String problems are among the most common in coding interviews. They combine multiple patterns — two pointers, sliding window, hash maps, and tries. In this article, you will learn the most important string patterns and how to recognize which one to use.
We show every example in Kotlin, Python, and Go.
String Basics
Before diving into patterns, remember these important facts:
- Python: Strings are immutable. Concatenation in a loop is O(n^2). Use
"".join()or a list. - Kotlin: Strings are immutable. Use
StringBuilderfor building strings. - Go: Strings are immutable byte slices. Use
strings.Builderfor efficient concatenation.
Pattern 1: Two Pointers on Strings
Use two pointers to check palindromes, reverse strings, and compare characters from both ends.
Valid Palindrome
Python:
def is_palindrome(s):
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
Kotlin:
fun isPalindrome(s: String): Boolean {
val cleaned = s.filter { it.isLetterOrDigit() }.lowercase()
var left = 0
var right = cleaned.length - 1
while (left < right) {
if (cleaned[left] != cleaned[right]) return false
left++
right--
}
return true
}
Go:
import "strings"
func isPalindrome(s string) bool {
s = strings.ToLower(s)
left, right := 0, len(s)-1
for left < right {
for left < right && !isAlphanumeric(s[left]) {
left++
}
for left < right && !isAlphanumeric(s[right]) {
right--
}
if s[left] != s[right] {
return false
}
left++
right--
}
return true
}
func isAlphanumeric(b byte) bool {
return (b >= 'a' && b <= 'z') || (b >= '0' && b <= '9')
}
Longest Palindromic Substring
Expand from center. For each character (and each pair of characters), expand outward while the characters match.
Python:
def longest_palindrome(s):
result = ""
def expand(left, right):
nonlocal result
while left >= 0 and right < len(s) and s[left] == s[right]:
if right - left + 1 > len(result):
result = s[left:right + 1]
left -= 1
right += 1
for i in range(len(s)):
expand(i, i) # Odd-length palindromes
expand(i, i + 1) # Even-length palindromes
return result
Time: O(n^2). Space: O(1).
Pattern 2: Sliding Window on Strings
Use a sliding window for substring problems involving frequency constraints.
Longest Substring Without Repeating Characters
Python:
def length_of_longest_substring(s):
char_index = {}
left = result = 0
for right in range(len(s)):
if s[right] in char_index and char_index[s[right]] >= left:
left = char_index[s[right]] + 1
char_index[s[right]] = right
result = max(result, right - left + 1)
return result
Find All Anagrams in a String
Find all start indices where an anagram of pattern p appears in string s.
Python:
from collections import Counter
def find_anagrams(s, p):
if len(p) > len(s):
return []
p_count = Counter(p)
s_count = Counter(s[:len(p)])
result = []
if s_count == p_count:
result.append(0)
for i in range(len(p), len(s)):
s_count[s[i]] += 1
left_char = s[i - len(p)]
s_count[left_char] -= 1
if s_count[left_char] == 0:
del s_count[left_char]
if s_count == p_count:
result.append(i - len(p) + 1)
return result
Kotlin:
fun findAnagrams(s: String, p: String): List<Int> {
if (p.length > s.length) return emptyList()
val pCount = IntArray(26)
val sCount = IntArray(26)
for (c in p) pCount[c - 'a']++
for (i in 0 until p.length) sCount[s[i] - 'a']++
val result = mutableListOf<Int>()
if (pCount.contentEquals(sCount)) result.add(0)
for (i in p.length until s.length) {
sCount[s[i] - 'a']++
sCount[s[i - p.length] - 'a']--
if (pCount.contentEquals(sCount)) result.add(i - p.length + 1)
}
return result
}
Time: O(n) where n = length of s. Space: O(1) for fixed alphabet.
Pattern 3: Hash Map Frequency Counting
Count character frequencies to solve anagram, grouping, and comparison problems.
Group Anagrams
Group strings that are anagrams of each other.
Python:
from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s))
groups[key].append(s)
return list(groups.values())
Go:
import "sort"
func groupAnagrams(strs []string) [][]string {
groups := map[string][]string{}
for _, s := range strs {
runes := []rune(s)
sort.Slice(runes, func(i, j int) bool { return runes[i] < runes[j] })
key := string(runes)
groups[key] = append(groups[key], s)
}
result := make([][]string, 0, len(groups))
for _, group := range groups {
result = append(result, group)
}
return result
}
Time: O(n * k log k) where n = number of strings, k = max string length. You can improve to O(n * k) by using a frequency count as the key.
Longest Repeating Character Replacement
Find the length of the longest substring with at most k character replacements.
Python:
def character_replacement(s, k):
count = {}
left = max_freq = result = 0
for right in range(len(s)):
count[s[right]] = count.get(s[right], 0) + 1
max_freq = max(max_freq, count[s[right]])
if (right - left + 1) - max_freq > k:
count[s[left]] -= 1
left += 1
result = max(result, right - left + 1)
return result
Time: O(n). Space: O(1).
Pattern 4: String Building
Build strings efficiently using a list (Python), StringBuilder (Kotlin), or strings.Builder (Go).
Encode and Decode Strings
Encode a list of strings into a single string and decode it back.
Python:
def encode(strs):
result = []
for s in strs:
result.append(f"{len(s)}#{s}")
return "".join(result)
def decode(s):
result = []
i = 0
while i < len(s):
j = s.index("#", i)
length = int(s[i:j])
result.append(s[j + 1:j + 1 + length])
i = j + 1 + length
return result
Kotlin:
fun encode(strs: List<String>): String {
val sb = StringBuilder()
for (s in strs) {
sb.append("${s.length}#$s")
}
return sb.toString()
}
fun decode(s: String): List<String> {
val result = mutableListOf<String>()
var i = 0
while (i < s.length) {
val j = s.indexOf('#', i)
val length = s.substring(i, j).toInt()
result.add(s.substring(j + 1, j + 1 + length))
i = j + 1 + length
}
return result
}
Pattern 5: Trie-Based String Problems
Use tries for prefix matching, autocomplete, and word search problems.
Word Search II
Find all words from a dictionary that exist in a 2D grid. Build a trie from the dictionary, then DFS on the grid.
Python:
class TrieNode:
def __init__(self):
self.children = {}
self.word = None
def find_words(board, words):
root = TrieNode()
for word in words:
node = root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.word = word
result = []
rows, cols = len(board), len(board[0])
def dfs(r, c, node):
if r < 0 or r >= rows or c < 0 or c >= cols:
return
char = board[r][c]
if char not in node.children:
return
node = node.children[char]
if node.word:
result.append(node.word)
node.word = None # Avoid duplicates
board[r][c] = "#" # Mark visited
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
dfs(r + dr, c + dc, node)
board[r][c] = char # Restore
for r in range(rows):
for c in range(cols):
dfs(r, c, root)
return result
KMP Algorithm for Pattern Matching (Simplified)
The KMP (Knuth-Morris-Pratt) algorithm finds a pattern in a text in O(n + m) time by precomputing a failure function that avoids re-scanning characters.
Python:
def kmp_search(text, pattern):
# Build failure function
lps = [0] * len(pattern)
length = 0
i = 1
while i < len(pattern):
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
elif length != 0:
length = lps[length - 1]
else:
lps[i] = 0
i += 1
# Search
i = j = 0
results = []
while i < len(text):
if pattern[j] == text[i]:
i += 1
j += 1
if j == len(pattern):
results.append(i - j)
j = lps[j - 1]
elif i < len(text) and pattern[j] != text[i]:
if j != 0:
j = lps[j - 1]
else:
i += 1
return results
Time: O(n + m). You rarely need to implement KMP in interviews, but knowing it exists shows depth.
Common Mistakes
String concatenation in a loop. O(n^2) in Python and Kotlin. Use join or StringBuilder.
Off-by-one errors in substring extraction. Python’s
s[i:j]excludes index j. Kotlin’ssubstring(i, j)also excludes j. Go’ss[i:j]excludes j.Forgetting case sensitivity. Convert to lowercase early if the problem is case-insensitive.
Not handling empty strings. Always check for empty input at the start.
Practice Problems
| Problem | Pattern | LeetCode # |
|---|---|---|
| Valid Palindrome | Two pointers | #125 |
| Longest Palindromic Substring | Expand from center | #5 |
| Longest Substring Without Repeating | Sliding window | #3 |
| Find All Anagrams | Sliding window | #438 |
| Group Anagrams | Hash map | #49 |
| Longest Repeating Character Replacement | Sliding window | #424 |
| Word Search II | Trie + DFS | #212 |
| Encode and Decode Strings | String building | #271 |
What’s Next?
Strings covered. The next article dives into Tree and Graph Patterns — DFS variants, BFS level-order tricks, path problems, and the most common tree/graph interview patterns.
Next: DSA Tutorial #21: Tree and Graph Patterns
Full series: DSA from Zero to Interview Ready