Day 12 of 30 days of Data Structures and Algorithms and System Design Simplified — Strings
Welcome back peeps. Hope all’s well. In this post we will cover Strings as follows —
What and Why Strings(in 2–3 sentences)?
How does Strings work?
Important Patterns and Techniques in Strings Questions
Most Important Questions with Solutions
Tips and Techniques to solve Strings Questions Fast.
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Strings
Importance : Very High
Let’s dive in!
What is Strings?
Python strings are arrays of bytes representing unicode characters. Strings in python are surrounded by either single quotation marks, or double quotation marks.
‘today’ is the same as “today”.
Example :
var1 = ‘Hello’
var2 = “Complete Python Course”
You can assign a multiline string to a variable by using three quotes.
Implementation —
str1 = "Welcome to complete Python Course"
str2 = 'Welcome to the complete Python Course'
str3 = """This is a
multiline
String"""
print(str1)
print(str2)
print(str3)Examples of Strings problems —
Longest Substring Without Repeating Characters
Longest Common Prefix
Longest Substring
Find subsequence
Word Search
Multiply strings
Analgrams
Palindromes
Reverse words
Isomorphic Strings
How does String work?
Strings are implemented as an array of characters with a special termination character, such as a null character, to indicate the end of the string. String manipulation functions and operators are commonly used to perform tasks such as concatenation, substring extraction, and search and replace operations on strings.
Some of the important String Methods that you should know —
String Indexing —
In python, Indexing is used to access individual characters of a string
Square brackets are used to access the character of the string using Index
Index starts with 0 , -1 refers to the last character, -2 refers to the second last character and so on
Example:
var[3]
var[-2]
String Slicing —
In python, Slicing is used to access a range of characters in the string. Slicing operator colon (:) is used
Example:
var[1:4]
var[:4]
Implementation —
s= "Captain America"
print(s[4])Output —
aImplementation 2 —
s= "Captain America"
print(s[1:5:2])Output —
atImplementation 3 —
print(s[::-1])Output —
aciremA niatpaCString Methods
- split() : Splits String from Left
Implementation —
a = "Welcome,,Friends,"
print(a.split(","))Output —
['Welcome', '', 'Friends', '']- splitlines() : Splits String at Line Boundaries
- startswith() : Checks if String Starts with the Specified String
- strip() : Removes Both Leading and Trailing Characters
Implementation —
a = "***Python***"
print(a.strip("*"))Output —
Python- swapcase() : swap uppercase characters to lowercase; vice versa
Implementation —
a = "Hi Homies"
print(a.swapcase())Output —
hI hOMIES- title() : Returns a Title Cased String
- translate() : returns mapped charactered string
- partition(sep) : Splits the string at the first occurrence of sep
Implementation —
a = "Complete.Python-course"print(a.partition("-"))
print(a.partition("."))Output —
('Complete.Python', '-', 'course')
('Complete', '.', 'Python-course')- isspace() : Checks Whitespace Characters
Implementation —
a = "\n\r"
print(a.isspace())Output —
True- istitle() : Checks for Titlecased String
- isupper() : returns if all characters are uppercase characters
- join() : Returns a Concatenated String
Implementation —
a = ","
print(a.join("CD"))Output —
C,D- ljust() : returns left-justified string of given width
Implementation —
x = "Python"
y = x.ljust(10, "*")
print(y)Output —
Python****- lower() : returns lowercased string
- lstrip() : Removes Leading Characters
Implementation —
a = "*****Python-----"
print(a.lstrip("*"))Output —
Python------ maketrans() : returns a translation table
- replace() : Replaces Substring Inside
Implementation —
a = "Welcome Aliens. Welcome to this world"print(a.replace("Welcome", "Hi"))Output —
Hi Aliens. Hi to this world- rindex() : Just like rfind() but raises ValueError when the substring sub is not found
Implementation —
a = "Hi World"print(a.rindex("d"))
print(a.rindex("W"))Output —
7 3
- rjust() : returns right-justified string of given width
- rstrip() : Removes Trailing Characters
- upper() : returns uppercased string
- zfill() : Returns a Copy of The String Padded With Zeros
Implementation —
a = "-124"
print(a.zfill(6))Output —
-00124- capitalize() : Converts first character to Capital Letter
Implementation —
a = "complete python course"
print(a.capitalize())Output —
Complete python course- casefold() : converts to case folded strings
Implementation —
a = "PYTHON"
print(a.casefold())Output —
python- center(): Pads string with specified character
Implementation —
a = "Python"
b = a.center(10, "*")
print(b)Output —
**Python**- index(): Returns Index of Substring
Implementation —
a = "Continent"
print(a.index("i"))
print(a.index("C"))
print(a.index("nent"))Output —
4 0 5
- isalnum(): Checks Alphanumeric Character
Implementation —
c = "456"
d = "$*%!!**"
print(c.isalnum())
print(d.isalnum())Output —
True
False- isalpha() : Checks if All Characters are Alphabets
Implementation —
c = "456"
d = "Python"
print(c.isalpha())
print(d.isalpha())Output —
False
True- isdecimal() : Checks Decimal Characters
Implementation —
c = u"\u00B10"
x = "10"
print(c.isdecimal())
print(x.isdecimal())Output —
False
True- isdigit() : Checks Digit Characters
Implementation —
c = "4567"
d = "1.65"
print(c.isdigit())
print(d.isdigit())Output —
True
False- isidentifier() : Checks for Valid Identifier
Implementation —
a = "_user/4567"
b = "for"
print(a.isidentifier())
print(b.isidentifier())Output —
False
True- islower() : Checks if all Alphabets in a String are Lowercase
- isnumeric() : Checks Numeric Characters
- isprintable() : Checks Printable Character
- count() : returns occurrences of substring in string
Implementation —
a = "Welcome to complete Python Course"print(a.count("c"))
print(a.count("o"))
print(a.count("Python"))Output —
2 5 1
- encode() : returns encoded string of given string
- endswith(): Checks if String Ends with the Specified Suffix
Implementation —
a = "Watermelon"
print(a.endswith("s"))
print(a.endswith("melon"))Output —
False
True- expandtabs() : Replaces Tab character With Spaces
- find(): Returns the index of first occurrence of substring
Implementation —
a = "Exercise"
print(a.find("r"))
print(a.find("e"))Output —
3 2
- format(): formats string into nicer output
- format_map() : Formats the String Using Dictionary
Important Patterns and Techniques in String Questions
Strings function just like list i.e using indexing. So, along with strings methods mentioned above know how to manipulate string indexes and most importantly slicing.
Important patterns and techniques in string questions include regular expressions, string manipulation, and algorithms such as the Knuth-Morris-Pratt algorithm for string matching.
Patterns → Questions like below belong to Strings( not limited to):
Word Break
Shortest distance from one string to other
Longest Substring Without Repeating Characters
Longest Common Prefix
Longest Substring
Find subsequence
Word Search
Multiply strings
Analgrams
Palindromes
Reverse words
Isomorphic Strings etc
Most Important Questions with Solutions
Note : New String questions with solutions are added everyday. So keep checking this post daily.
Golden rule is — Learn by doing/implementing
In this we will see most important String questions.
Palindrome or not
Question —
A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward. Alphanumeric characters include letters and numbers.
Given a string s, return true if it is a palindrome, or false otherwise.
Example —
Input: s = "race a car"
Output: falseSolution:
Main Logic/Idea —
The main logic is to first check if the character at index t or v is alphanumeric or not. If not alphanumeric then keep incrementing/decrementing the pointers accordingly. Keep comparing the characters till t
Implementation —
class Solution:
def isPalindrome(self, s: str) -> bool:
t, v = 0,len(s)-1
while t<v :
while t< v and not self.checkAlpha(s[t]):
t+=1
while v > t and not self.checkAlpha(s[v]):
v -=1
if s[t].lower() != s[v].lower():
return False
t,v = t+1,v-1
return True
def checkAlpha(self,n):
return (ord('0') <= ord(n) <= ord('9') or
ord('A') <= ord(n) <= ord('Z') or
ord('a') <= ord(n) <= ord('z'))Question Link
Similar Pattern —
Maximum Product of the Length of Two Palindromic Subsequences
Find First Palindromic String in the Array
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Valid Parentheses
Question —
Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
- Open brackets must be closed by the same type of brackets.
- Open brackets must be closed in the correct order.
- Every close bracket has a corresponding open bracket of the same type.
Example :
Input: s = "()[]{}"
Output : TrueSolution :
Main Logic/Idea —
The main logic here is using hash map to map the close parentheses to open parentheses, append to the stack and using pop the similar match parentheses while traversing through the stack.
Implementation —
def isValid(self, s: str) -> bool:
parenthesisMap = { ")":"(", "]":"[", "}":"{" }
ans = []
for i in s:
if i not in parenthesisMap:
ans.append(i)
continue
if not ans or ans[-1] != parenthesisMap[i]:
return False
ans.pop()
return not ansQuestion Link
Similar Pattern —
Check If Word Is Valid After Substitutions
Check if a Parentheses String Can Be Valid
Move Pieces to Obtain a String
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Find the Index of the First Occurrence in a String
Question —
Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example :
Input: haystack = "sadbutsad", needle = "sad"
Output: 0Solution :
Main Logic/Idea —
The main logic is know how to use index string method and once the index is found then return the index else return -1.
Implementation —
def strStr(self, haystack: str, needle: str) -> int:
if needle in haystack :
return haystack.index(needle)
return -1Question Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Tips and Techniques to solve Strings Questions Fast.
The most important thing to know before you solve any string question —
Strings methods ( covered above)
Indexing and Slicing ( covered above)
That’s it for now. Day 13: Linked List coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time. Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
