Strings & String Algorithms: Immutability, Building, Searching, and Classic Patterns

In plain words — the granite engraving analogy

Imagine text engraved in granite. You can read any letter instantly (O(1) by position), but you cannot add a letter to the middle — you'd have to chisel out the whole inscription and re-engrave it from scratch. That's an immutable string. Every time you 'change' one in code, the language carves a brand new piece of granite. Now imagine a helper with a scratch pad: they accumulate your edits in pencil, and only engrave one final version. That's a string builder, and it's the key to avoiding O(n²) performance.

Strings as character arrays

A string is, structurally, just an array of characters — so everything from the last lesson applies: O(1) access by index, O(n) search, cache-friendly scans. But strings add two twists that earn them their own lesson: immutability, which changes the cost model in ways that bite real programs, and a family of classic algorithms (searching, matching, transforming text) that show up constantly in both interviews and production code.

Immutability and the hidden O(n²)

In Java, Python, JavaScript, C#, Kotlin and most modern languages, a string cannot be modified after creation. 'Changing' a character or appending a suffix actually allocates a new string and copies the old contents into it. Immutability buys real benefits — strings can be shared safely across threads, used as hash-table keys, and interned — but it means every concatenation is an O(n) copy of the combined length.

The classic trap follows immediately: building a string by appending in a loop. Appending one character to a string of length k copies k + 1 characters; doing that n times copies 1 + 2 + … + n ≈ n²/2 characters. A loop that 'just adds a character each time' is quietly O(n²). For n = 100,000 that's five billion character copies to build one modest string.

IMMUTABLE CONCATENATION — why it's O(n²)

Iteration 1: result = ""  + "a"   → allocates "a"        (1 copy)
Iteration 2: result = "a" + "b"   → allocates "ab"       (2 copies)
Iteration 3: result = "ab" + "c"  → allocates "abc"      (3 copies)
…
Iteration n: result = (n-1 chars) + "z" → allocates n-char string (n copies)

Total copies: 1 + 2 + 3 + … + n = n(n+1)/2 ≈ n²/2   → O(n²)

STRING BUILDER — why it's O(n)

Buffer is a dynamic array of characters (amortized O(1) append):
  append("a") → buffer: [a]
  append("b") → buffer: [a,b]
  append("c") → buffer: [a,b,c]
  …
  append("z") → buffer: [a,b,c,…,z]
  join()      → one final copy of n chars          → O(n)

Total: n × O(1) amortized + O(n) join = O(n) ✓

Core operation costs

Substring search: from brute force to KMP

The defining string problem: find pattern P (length m) inside text T (length n). Brute force tries every starting position: align P at T[0], compare character by character; on mismatch, slide one right and start over. Worst case O(n·m) — pathological on repetitive inputs like searching 'aaab' in 'aaaaaaaaaa…'. In practice it's often fine, because on random text mismatches happen fast.

Brute-force substring search:

function search(T, P):           # T = text, P = pattern
    n ← length(T),  m ← length(P)
    for s from 0 to n - m:       # try each starting position
        match ← true
        for i from 0 to m - 1:
            if T[s + i] ≠ P[i]:
                match ← false
                break
        if match: return s        # found at index s
    return -1                    # not found

Time: O(n × m) worst case (e.g. T = "aaa…ab", P = "aab")
Space: O(1)

1. The waste brute force repeats: after matching 'aaab' against 'aaaa…' and failing on the 'b', brute force slides one step and re-compares the same 'aaa' prefix it already verified.
2. KMP's insight: preprocess the pattern into a failure table. For each prefix of P, record the length of the longest proper prefix that is also a suffix. On a mismatch at P[i], shift the pattern by what the table dictates — the text pointer never moves backward.
3. Result: every text character is examined O(1) times → O(n + m) guaranteed, with O(m) extra space for the failure table.
4. Rabin-Karp variant: instead of character comparison, compute a rolling hash of the current text window. Compare hash values in O(1), recompute incrementally as the window slides. O(n + m) expected, O(nm) worst (hash collisions), and naturally extends to multi-pattern search.

KMP failure table example — pattern "ABABC"

Index:   0   1   2   3   4
Pattern: A   B   A   B   C
Fail:    0   0   1   2   0

Reading: fail[i] = length of longest proper prefix of P[0..i]
         that is also a suffix of P[0..i]

"AB"   → prefix "A" is also suffix? No  → fail[1] = 0
"ABA"  → "A" is both prefix and suffix  → fail[2] = 1
"ABAB" → "AB" is both prefix and suffix → fail[3] = 2
"ABABC"→ no match                       → fail[4] = 0

On mismatch at pattern index 3 (expecting 'B', got 'X'):
  skip to fail[2] = 1 (pattern index 1), text pointer stays put ✓

Classic patterns, worked

Pattern 1: Reverse a string — the two-pointer template

Convert to a mutable character array, then set left = 0 and right = n − 1; swap the characters and move both pointers inward until they cross. O(n) time, O(n) space for the char array (O(1) extra beyond the array itself).

function reverseString(s):
    chars ← toCharArray(s)     # O(n) copy from immutable string
    left  ← 0
    right ← length(chars) - 1
    while left < right:
        swap(chars[left], chars[right])
        left  ← left  + 1
        right ← right - 1
    return join(chars)         # O(n) to build result string

Trace on "hello":  h e l l o
                   ↑       ↑  swap h↔o → o e l l h
                     ↑   ↑    swap e↔l → o l l e h
                       ↑      left==right, stop
Result: "olleh" ✓

Pattern 2: Anagram check — the frequency counting template

Are two strings rearrangements of each other? Sorting both and comparing works in O(n log n). The better pattern: count characters. Walk the first string incrementing a count per character, walk the second decrementing; if any count goes negative (or the lengths differ), they're not anagrams. O(n) time, O(1) extra space for a fixed-size alphabet array.

function isAnagram(s, t):
    if length(s) ≠ length(t): return false
    count ← array of 26 zeros   # for 'a'..'z'

    for c in s: count[c - 'a'] += 1   # increment
    for c in t: count[c - 'a'] -= 1   # decrement

    for each freq in count:
        if freq ≠ 0: return false
    return true

Example: s = "listen",  t = "silent"
After s-pass: l=1, i=1, s=1, t=1, e=1, n=1
After t-pass: all back to 0 → anagram ✓

Example: s = "rat", t = "car"
After s-pass: r=1, a=1, t=1
After t-pass: r=0, a=0, t=1, c=-1 → not anagram ✓

Pattern 3: Palindrome check — two pointers with filtering

Compare characters from both ends moving inward; any mismatch means not a palindrome. Real variants add filtering (skip non-alphanumerics, normalize case) — do that with pointer advancement, not by building a cleaned copy, to keep O(1) extra space.

function isPalindrome(s):
    left  ← 0
    right ← length(s) - 1
    while left < right:
        while left < right and not isAlphanumeric(s[left]):
            left  ← left  + 1          # skip non-alphanum
        while left < right and not isAlphanumeric(s[right]):
            right ← right - 1
        if toLower(s[left]) ≠ toLower(s[right]):
            return false
        left  ← left  + 1
        right ← right - 1
    return true

Example: "A man, a plan, a canal: Panama"
  Pointers skip commas and spaces, compare a↔a, m↔m, … ✓
  O(n) time, O(1) extra space

Pattern 4: Longest palindromic substring — expand from center

Expand outward from each of the 2n − 1 possible centers (each character, and each gap between characters, so even-length palindromes aren't missed), tracking the widest expansion. O(n²) time, O(1) space. The idea of 'expand from each candidate center' recurs in interval and sliding-window problems.

Common pitfalls

• Concatenating in a loop. The O(n²) trap from above. Reach for a builder/join the moment string-building enters a loop.
• Forgetting slices copy. Taking a substring inside a loop can turn an O(n) algorithm into O(n²). Track index ranges instead of materializing substrings.
• Comparing strings with identity instead of equality. In several languages, == on strings may compare references, not contents (or vice versa). Know your language's rule cold.
• Assuming one byte = one character. Unicode breaks indexing, length, and reversal assumptions the instant text leaves ASCII.
• Ignoring the alphabet-size constant. 'O(1) space because the count array is size 26' is only valid when the problem really is lowercase English. For general Unicode, use a hash map and say O(k).
• Off-by-one in sliding window string problems. The window length formula is right - left + 1 (inclusive both ends). Getting this wrong by one position corrupts the entire search.

Practice problems

1. First non-repeating character. Given a string, find the index of the first character that appears exactly once. Solve it in O(n) time with O(1) space (hint: two passes — count frequencies, then find the first with count 1).
2. Group anagrams. Given a list of words, group all anagrams together. Solve in O(n × k log k) time where k is the average word length (sort each word as a key). Then think about whether you can do O(n × k) using frequency tuples as keys.
3. Minimum window substring. Given strings S and T, find the shortest substring of S that contains all characters of T. The sliding window approach runs in O(n + m). This is a hard problem worth tracing carefully on paper before coding.

Key takeaways

• A string is a character array with immutability layered on top in most languages — reads are cheap, 'writes' allocate copies.
• Repeated concatenation is O(n²); buffer-then-join is O(n). This is the most practically valuable fact in the lesson.
• Substring search runs from O(n·m) brute force to O(n + m) KMP; the shared idea is preprocessing the pattern so mismatches skip instead of restart.
• Two templates — two pointers and frequency counting — solve most interview string problems: reversal, palindromes, anagrams, uniqueness.
• Unicode invalidates naive index/length/reverse assumptions; know when your 'string' is really bytes.

Next, the course leaves contiguous memory behind: linked lists, where elements live anywhere and pointers hold the structure together. Practice string-algorithm questions offline in the **AI Learning app**.

AI Learning: AI/ML/DS Q&A

A private, offline app to learn Artificial Intelligence, Machine Learning & Data Science at your own level: ~10,000 Q&A, illustrated guides, cheat sheets, quizzes and mock tests.

Coming soon toGoogle Play