Strings are in almost every coding interview. Master the core techniques — sliding window, two pointers, hashing — and you'll handle any string problem.
A string is a sequence of characters stored as an array of bytes. In most languages, strings are immutable — operations like concatenation create new strings rather than modifying the original.
s = "hello"
s[0] = "H" # ❌ TypeError — strings are immutable in Python
s = "H" + s[1:] # ✅ creates a new string "Hello"Implication: Concatenating strings in a loop is O(n²) — use a list and join() instead.
# ❌ O(n²) — creates a new string each iteration
result = ""
for char in chars:
result += char
# ✅ O(n) — join at the end
result = "".join(chars)| Operation | Python | Time |
|---|---|---|
| Length | len(s) | O(1) |
| Access char | s[i] | O(1) |
| Slice | s[i:j] | O(j-i) |
| Concatenate | s1 + s2 | O(n) |
| Find substring | s.find(t) | O(n·m) |
| Split | s.split() | O(n) |
| Join | "".join(arr) | O(n) |
| Reverse | s[::-1] | O(n) |
| Lower/Upper | s.lower() | O(n) |
Use when checking palindromes, reversing, or comparing from both ends.
def is_palindrome(s):
# Keep only alphanumeric, lowercase
s = "".join(c.lower() for c in s if c.isalnum())
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
is_palindrome("A man, a plan, a canal: Panama") # Truedef reverse_words(s):
return " ".join(s.split()[::-1])
reverse_words(" hello world ") # "world hello"Use for substrings with constraints — longest, shortest, with/without repeats.
def length_of_longest_substring(s):
char_index = {}
left = max_len = 0
for right, char in enumerate(s):
if char in char_index and char_index[char] >= left:
left = char_index[char] + 1 # shrink window
char_index[char] = right
max_len = max(max_len, right - left + 1)
return max_len
length_of_longest_substring("abcabcbb") # 3 ("abc")from collections import Counter
def min_window(s, t):
need = Counter(t)
missing = len(t)
left = start = end = 0
for right, char in enumerate(s, 1):
if need[char] > 0:
missing -= 1
need[char] -= 1
if missing == 0: # valid window found
# shrink from left
while need[s[left]] < 0:
need[s[left]] += 1
left += 1
if end ==
Use for anagrams, character frequency problems.
def is_anagram(s, t):
return Counter(s) == Counter(t)
# Or without Counter:
def is_anagram(s, t):
if len(s) != len(t): return False
count = [0] * 26
for a, b in zip(s, t):
count[ord(a) - ord('a')] += 1
count[ord(b) - ord('a')] -= 1
return all(c == 0 for c in count)from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # canonical form
groups[key].append(s)
return list(groups.values())
group_anagrams(["eat","tea","tan","ate","nat","bat"])
# [["eat","tea","ate"], ["tan","nat"], ["bat"]]For finding a pattern in a string efficiently — O(n+m) instead of O(n·m).
def kmp_search(text, pattern):
# Build failure function
m = len(pattern)
fail = [0] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = fail[j-1]
if pattern[i] == pattern[j]:
j += 1
fail[i] = j
# Search
j = 0
results = []
for i, char in enumerate(text):
while
| Problem | Pattern | Key insight |
|---|---|---|
| Valid palindrome | Two pointers | Skip non-alphanumeric |
| Longest substring no repeat | Sliding window + hash | Track last seen index |
| Minimum window substring | Sliding window | Shrink when valid |
| Group anagrams | Hashing | Sorted string as key |
| Valid anagram | Frequency count | 26-char array |
| Longest palindromic substring | Expand around center | Check odd and even length |
| String compression | Two pointers | Count consecutive chars |
| Encode/decode strings | Delimiter encoding | Length-prefix protocol |
def longest_palindrome(s):
result = ""
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return s[left+1:right]
for i in range(len(s)):
odd = expand(i, i) # odd length: "aba"
even = expand(i, i+1) # even length: "abba"
if len(odd) > len(result): result = odd
if len(even) >
join() not += in loops