λDSA Learning Hubpart of DSA Atlas

Strings

Beginner~3h · 7 lessons12 practice problems

Immutable character arrays: palindromes, anagrams, frequency counting, substring vs subsequence, and the classic pattern-matching algorithms.

0 of 7 lessons checked off

Introduction

What it is

  • A string is an immutable sequence of characters — effectively a read-only array. Every 'modification' in Python builds a new string.
  • Two definitions interviews constantly test: a substring is contiguous ('cde' in 'abcdef'); a subsequence keeps order but may skip ('ace' in 'abcdef').

Why it matters

  • String questions are a permanent fixture of interviews because they combine array technique with hashing (frequency maps), two pointers (palindromes), sliding windows (longest substring …), and DP (edit distance).
  • Immutability has real complexity consequences: s += ch in a loop is O(n²), the single most common performance bug in Python string code.

How it works

  • Index and slice like arrays: s[i] is O(1), s[a:b] copies O(b−a).
  • Count characters with a hash map (or Counter) to answer anagram/frequency questions in O(n).
  • Compare from both ends with two pointers for palindromes; build results in a list and ''.join once.

Where it's used

  • Search engines, DNA sequence analysis, spell checkers, log parsing, and every compiler lexer are string algorithms at industrial scale.

In interviews

  • Valid anagram / group anagrams (frequency signatures), valid palindrome (two pointers), longest substring without repeats (window), longest common prefix, and pattern matching (KMP / Rabin-Karp) as advanced follow-ups.
Analogy: A string is a word carved in stone: you can read any letter instantly, but 'changing' one means carving a whole new stone — so plan your edits and carve once.

Interactive diagram

Compare outermost characters and walk inward — the canonical O(n)/O(1) string technique.

Is "racecar" a palindrome?

Compare the outermost characters and walk inward. Any mismatch answers 'no' immediately — no need to look at the rest.

Lessons in this topic

Check off lessons as you go — your progress is saved in this browser.

  1. String traversal and immutability

    Indexing, slicing costs, and why strings can't change in place.

    15 min
  2. Character frequency

    Counter / dict signatures; the tool behind anagram questions.

    15 min
  3. Palindromes

    Two-pointer check, ignoring non-alphanumerics, and expand-around-centre.

    20 min
  4. Anagrams

    Sorted-string vs frequency-map signatures and their costs.

    15 min
  5. Substrings vs subsequences

    Contiguous vs order-preserving; counts (n(n+1)/2 vs 2ⁿ) and which patterns apply.

    15 min
  6. Longest common prefix

    Vertical scanning and why sorting first can shortcut.

    15 min
  7. Pattern searching: KMP, Rabin-Karp, Z (overview)

    Beating O(n·m): failure functions, rolling hashes, Z-arrays.

    35 min

Operations

Character frequency and anagram check

Two strings are anagrams exactly when their frequency signatures match — one dict, one pass each.

Character frequency and anagram check
from collections import Counterdef is_anagram(s: str, t: str) -> bool:    """True if t rearranges s. O(n) time, O(k) space (k = alphabet)."""    if len(s) != len(t):        return False    return Counter(s) == Counter(t)def group_anagrams(words: list[str]) -> list[list[str]]:    """Group words sharing a frequency signature. O(total chars)."""    groups: dict[tuple[int, ...], list[str]] = {}    for word in words:        signature = [0] * 26        for ch in word:            signature[ord(ch) - ord("a")] += 1        groups.setdefault(tuple(signature), []).append(word)    return list(groups.values())
Time: O(n) per string — vs O(n log n) for the sort-based signatureSpace: O(k) for the alphabet-size counter

Edge cases

  • Length mismatch: answer immediately, no counting needed.
  • Unicode input makes the 26-slot trick wrong — fall back to Counter.
  • Empty strings are anagrams of each other.

Common mistakes

  • Sorting both strings (O(n log n)) and calling it optimal when counting is O(n).
  • Using a list as a dict key — lists aren't hashable; convert to tuple.

Valid palindrome (two pointers)

Walk from both ends toward the middle; any mismatch ends it. Filters (case, punctuation) happen on the fly.

Is "racecar" a palindrome?

Compare the outermost characters and walk inward. Any mismatch answers 'no' immediately — no need to look at the rest.

def is_palindrome(s: str) -> bool:    """Alphanumeric palindrome check, case-insensitive. O(n)/O(1)."""    left, right = 0, len(s) - 1    while left < right:        if not s[left].isalnum():            left += 1        elif not s[right].isalnum():            right -= 1        elif s[left].lower() != s[right].lower():            return False        else:            left += 1            right -= 1    return True
Time: O(n)Space: O(1) — versus O(n) for the s == s[::-1] one-liner

Edge cases

  • Empty string and single characters are palindromes.
  • Strings of only punctuation reduce to empty — True.
  • Mixed case must be normalised before comparing.

Common mistakes

  • Using s == s[::-1] when the interviewer asks for O(1) space.
  • Advancing both pointers when skipping a non-alphanumeric character — only the offending side moves.

Longest common prefix

Compare column by column across all words; stop at the first disagreement or the shortest word's end.

Longest common prefix
def longest_common_prefix(words: list[str]) -> str:    """Vertical scan. O(total characters compared)."""    if not words:        return ""    for col, ch in enumerate(words[0]):        for word in words[1:]:            if col == len(word) or word[col] != ch:                return words[0][:col]    return words[0]
Time: O(S) where S = sum of compared charactersSpace: O(1)

Edge cases

  • Empty list → empty prefix.
  • Any empty string in the list → empty prefix.
  • Identical words → the whole word.

Common mistakes

  • Comparing only the first and last words without sorting first (that shortcut requires sorting).
  • Index error by not checking col against each word's length.

KMP pattern search (failure function)

Precompute, for each pattern prefix, the longest proper prefix that is also a suffix — then never re-examine matched text.

KMP pattern search (failure function)
def kmp_search(text: str, pattern: str) -> int:    """Index of first occurrence of pattern in text, else -1.    O(n + m) — the two-pointer scan never moves backwards in text."""    if not pattern:        return 0    # failure[i] = length of longest proper prefix of pattern[:i+1]    # that is also a suffix of it    failure = [0] * len(pattern)    k = 0    for i in range(1, len(pattern)):        while k > 0 and pattern[i] != pattern[k]:            k = failure[k - 1]        if pattern[i] == pattern[k]:            k += 1        failure[i] = k    matched = 0
Time: O(n + m) vs O(n·m) naiveSpace: O(m) for the failure table

Edge cases

  • Empty pattern matches at index 0.
  • Pattern longer than text → −1.
  • Repetitive patterns like 'aaaa' are exactly where naive matching degrades and KMP shines.

Common mistakes

  • Rebuilding the failure table with nested loops (making it O(m²)).
  • Resetting matched to 0 on mismatch instead of failure[matched−1] — that discards the whole point of KMP.

Complexity analysis

OperationBestAverageWorstSpace
Index s[i]O(1)O(1)O(1)—
Slice s[a:b]O(b−a)O(b−a)O(n)O(b−a)
Concat s + tO(n+m)O(n+m)O(n+m)O(n+m)
''.join(parts)O(total)O(total)O(total)O(total)
Anagram check (Counter)O(n)O(n)O(n)O(k)
KMP searchO(n+m)O(n+m)O(n+m)O(m)

n, m = string lengths; k = alphabet size. The join row is why builders beat += loops.

Python implementation

Production-quality code with type hints, validation, and docstrings.

A StringBuilder: turning O(n²) concatenation into O(n)
class StringBuilder:    """Accumulate parts in a list; materialise once with build().    Mirrors what Java's StringBuilder does and what ''.join enables."""    def __init__(self) -> None:        self._parts: list[str] = []        self._length = 0    def append(self, text: str) -> "StringBuilder":        if not isinstance(text, str):            raise TypeError("StringBuilder.append expects a str")        self._parts.append(text)        self._length += len(text)        return self                      # allow chaining    def __len__(self) -> int:        return self._length

What interviewers expect you to know

Definitions to state precisely

  • Substring: contiguous slice — there are n(n+1)/2 of them. Subsequence: order-preserving selection — there are 2ⁿ.
  • Anagram: same multiset of characters — equal frequency signatures.
  • Python strings are immutable: every edit allocates.

Frequent follow-ups

  • "What if it's Unicode?" — alphabet-size arrays (26 slots) stop working; switch to a dict/Counter and say so.
  • "Can you avoid the O(n) reversed copy?" — two pointers give O(1) space.
  • "How would you search many patterns in one text?" — that's Aho-Corasick / trie territory; naming it is enough at most levels.

How to explain string problems

  • Classify the question out loud: frequency (hash), symmetry (two pointers), contiguous constraint (window), alignment/edits (DP). The classification is most of the answer.
  • Mention the += trap unprompted when building output — interviewers at Python shops listen for it.

Common mistakes

String concatenation in a loop

result += ch copies everything so far on every iteration: O(n²). Append to a list and ''.join once.

Confusing substring with subsequence

Sliding window solves substring ('contiguous') problems; subsequence problems usually need DP or greedy — the word in the prompt decides the technique.

Forgetting normalisation

Case, spaces, and punctuation silently break palindrome/anagram checks. Ask what counts as a character before coding.

Reversing when O(1) space was requested

s[::-1] allocates a full copy. The two-pointer scan does the same job without it.

Assuming 26 lowercase letters

signature[ord(c) − 97] crashes on 'É'. State the assumption or use a dict.

Practice problems

Hand-picked from the 355-problem DSA Atlas. Reveal hints and solutions progressively; mark and bookmark as you solve.

Easy (1)

Medium (7)

Hard (4)

Topic quiz

5 questions across concepts, code output, complexity, and scenarios. Answer all, then submit for explanations.

  1. Complexity1. What is the total cost of building an n-character string with `s += ch` in a loop?
  2. Concept2. 'ace' relative to 'abcde' is…
  3. Code output3. What does this print?
    from collections import Counterprint(Counter("listen") == Counter("silent"))
  4. Scenario4. You need the first occurrence of a 10⁴-char pattern in a 10⁷-char text, worst case guaranteed fast. Best tool?
  5. Concept5. Best O(1)-space way to verify 'A man, a plan, a canal: Panama' is a palindrome?
0 of 5 answered

Frequently asked questions

Why are Python strings immutable at all?

Immutability makes strings hashable (usable as dict keys), thread-safe, and safely shareable without defensive copies. The cost is copy-on-modify — hence the join idiom.

Do I need to memorise KMP for interviews?

For most companies, recognising when naive matching degrades and naming KMP/Rabin-Karp is enough; implementing the failure function from scratch is a senior/competitive-level ask. Understand it once so you can reason about it.

Counter vs sorting for anagrams — which should I lead with?

Counter: O(n) beats O(n log n), and it generalises to 'group anagrams' via frequency-tuple keys. Mention sorting as the simpler-but-slower alternative.

Summary & cheat sheet

Key takeaways

  • Strings are immutable arrays: reads O(1), edits allocate.
  • Frequency map = anagram tool; two pointers = palindrome tool; window = 'longest substring' tool.
  • Substring is contiguous, subsequence is not — the prompt's word choice picks your technique.
  • Build output in a list, join once.

Formulas & cheat sheet

  • Substrings of length-n string: n(n+1)/2 (+1 empty)
  • Subsequences: 2ⁿ
  • KMP: O(n + m) with failure[i] = longest proper prefix of p[:i+1] that is also its suffix

Interview checklist

  • I can write the two-pointer palindrome check with filters.
  • I can group anagrams with a frequency-tuple key.
  • I can say why += in a loop is O(n²) and what to do instead.
  • I can define substring vs subsequence without hesitation.