String Problems

Strings appear in almost every coding round: checking passwords, cleaning names, comparing words, compressing text. A string is really an array of characters, so everything from Arrays & Dynamic Arrays applies, with one big difference: Python strings cannot be changed.

In this lesson you will learn what immutability means for performance, and then solve four classic kinds of string problem with the patterns that interviewers expect: counting, two pointers, frequency maps and grouping.

Strings are immutable arrays

A Python string stores a sequence of Unicode characters. Reading s[i] is O(1) and len(s) is O(1), like a list. But you cannot change a character in place. Every "change" builds a new string.

city = "Kanpur"
try:
    city[0] = "J"
except TypeError as err:
    print("Error:", err)

fixed = "J" + city[1:]          # builds a brand new string
print(city, fixed)

# Building a long string: collect the parts, then join once
parts = []
for n in range(1, 6):
    parts.append(f"Table {n}")
print(", ".join(parts))

Error: 'str' object does not support item assignment
Kanpur Janpur
Table 1, Table 2, Table 3, Table 4, Table 5

Since each + makes a new string, a loop like result = result + piece may copy the growing result again and again, which is O(n²) in the worst case. CPython can sometimes avoid the copy, but you should not rely on that. The safe pattern is to collect pieces in a list and call "".join(parts) once, which is O(total length).

Pattern 1: counting characters (anagrams)

Two words are anagrams if they use exactly the same letters the same number of times, such as "listen" and "silent". There are two common solutions:

from collections import Counter

def anagram_by_sorting(a, b):       # O(n log n)
    return sorted(a) == sorted(b)

def anagram_by_counting(a, b):      # O(n)
    return Counter(a) == Counter(b)

pairs = [("listen", "silent"), ("night", "thing"), ("rohtak", "karoht"), ("pune", "puna")]
for a, b in pairs:
    print(a, b, anagram_by_sorting(a, b), anagram_by_counting(a, b))

print(Counter("banana"))

listen silent True True
night thing True True
rohtak karoht True True
pune puna False False
Counter({'a': 3, 'n': 2, 'b': 1})

Counter from the collections module builds a dictionary of character counts in one pass. Counting is the faster solution, O(n) against O(n log n) for sorting. Sorting is shorter to write and is fine when the words are short, so mention both in an interview and explain the trade-off.

Pattern 2: two pointers (palindromes)

A palindrome reads the same forwards and backwards, like "Malayalam" or "Nitin". The easy check is s == s[::-1], but it builds a reversed copy (O(n) extra space). The two-pointer method uses one index at each end, moving inwards, and needs no copy. It can also skip spaces and punctuation as it goes.

def is_palindrome(text):
    left, right = 0, len(text) - 1
    while left < right:
        if not text[left].isalnum():
            left += 1
        elif not text[right].isalnum():
            right -= 1
        elif text[left].lower() != text[right].lower():
            return False
        else:
            left += 1
            right -= 1
    return True

for phrase in ["Malayalam", "Nitin", "Step on no pets!", "Pune", "A man, a plan, a canal: Panama"]:
    print(phrase, "->", is_palindrome(phrase))

Malayalam -> True
Nitin -> True
Step on no pets! -> True
Pune -> False
A man, a plan, a canal: Panama -> True

Each character is visited at most once, so the time is O(n) and the extra space is O(1). You will use two pointers on many more problems in Two Pointers & Sliding Window.

Pattern 3: first unique character

A coupon system wants the first character in a code that appears only once. A nested loop that counts each character again is O(n²). Counting once, then scanning once, is O(n):

from collections import Counter

def first_unique(code):
    counts = Counter(code)
    for index, ch in enumerate(code):
        if counts[ch] == 1:
            return index, ch
    return -1, None

print(first_unique("DIWALI2026DIWALI"))
print(first_unique("SALESALE"))

(7, '0')
(-1, None)

Every letter of DIWALI repeats and 2 appears twice in 2026, so the first unique character is 0 at index 7. This "count first, then scan" idea is very common. Two passes of O(n) are still O(n).

Pattern 4: grouping runs (run-length encoding)

Run-length encoding compresses a string by writing each run of repeated characters as the character and its count, so "AAABBC" becomes "A3B2C1". A scoreboard that stores ball-by-ball results, such as "..1144...6", compresses well this way.

from itertools import groupby

def encode(text):
    parts = []
    for ch, run in groupby(text):
        parts.append(f"{ch}{len(list(run))}")
    return "".join(parts)

def encode_by_hand(text):
    if not text:
        return ""
    parts = []
    current, count = text[0], 1
    for ch in text[1:]:
        if ch == current:
            count += 1
        else:
            parts.append(f"{current}{count}")
            current, count = ch, 1
    parts.append(f"{current}{count}")        # do not forget the last run
    return "".join(parts)

overs = "..1144...6"
print(encode(overs))
print(encode_by_hand(overs))
print(repr(encode_by_hand("")))

.21242.361
.21242.361
''

itertools.groupby() groups consecutive equal items, which is exactly a run. The hand-written version shows the logic an interviewer wants to see, including the two classic traps: forgetting the last run and crashing on an empty string. The last line uses repr() so you can see that an empty string encodes to an empty string ''.

Common mistakes

• Building strings with += in a loop. Collect parts in a list and join them once.
• Forgetting case and spaces. "Nitin" is a palindrome only if you compare lowercase letters. Clarify the rules before coding.
• Using str.count() inside a loop. Each call scans the whole string, so the loop becomes O(n²). Count once with Counter.
• Missing the empty string and one-character string. Always test them.

Key points

• Strings are immutable arrays of characters: indexing is O(1), but every change builds a new string.
• Use "".join(parts) to build long strings in O(n).
• Counting characters with Counter (or a 26-slot array) solves anagram and frequency problems in O(n).
• Two pointers check palindromes in O(n) time and O(1) extra space.
• itertools.groupby() groups consecutive runs; always handle the last run and the empty string.

def is_rotation(a, b):
    return len(a) == len(b) and b in a + a

print(is_rotation("PUNE", "NEPU"))
print(is_rotation("PUNE", "NUPE"))
print(is_rotation("GOA", "GOA"))

True
False
True