Lesson 4 · Linear structures

Strings and Substring Algorithms

Strings are arrays of characters, but their use cases—parsing, searching, and natural language—demand specialized algorithms. Because strings are often immutable, seemingly simple concatenations can hide hidden O(N) penalties.

What is a String?

A string is a sequence of text units, but the representation is language-specific. A C++ std::string stores bytes, Java String uses UTF-16 code units, and Python exposes Unicode text while hiding its internal storage. One displayed character can occupy multiple bytes or code units.

In languages like Python and Java, strings are immutable. This means once a string is created, you cannot change a single character inside it; you must allocate a completely new string instead.

A sequence of characters stored contiguously
Usually immutable (cannot be modified in-place)
Characters are mapped using encodings like ASCII or Unicode

Why immutability matters

Because strings are immutable, adding a single character to a string of length N requires copying all N characters into a new memory location. Doing this in a loop results in an accidental O(N²) time complexity.

To fix this, modern programs collect substrings into a mutable array or a 'String Builder' and join them all together in a single O(N) operation at the very end.

str = str + char inside a loop is O(N²)
Use list.append() then ''.join() in Python
Use StringBuilder in Java or C#

Key reference

Terms, operations, and practical uses

Core vocabulary

Character EncodingA standard (like ASCII or UTF-8) that assigns numerical values to characters so they can be stored in memory.
ImmutabilityA property where an object's state cannot be modified after it is created. Any 'modification' actually returns a new object.
SubstringA contiguous sequence of characters within a string (e.g., 'ell' is a substring of 'hello').

Algorithms

KMP AlgorithmA pattern matching algorithm that preprocesses the search word to avoid re-evaluating matched characters, running in O(N+M) time.
Rabin-KarpA pattern matching algorithm that uses a rolling hash function to quickly filter out impossible matches.
Two PointersA common technique for string problems like checking palindromes by moving pointers from both ends towards the center.

Best practices

String BuildersMutable objects used to efficiently construct strings by appending characters without allocating new memory each time.
Character ArraysConverting an immutable string into an array of characters (e.g., list(str)) to perform in-place modifications.
O(1) Length CheckMost modern languages store the length of the string as a property, making len(str) an O(1) operation.

Code example

Check if a string is a palindrome

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
print(is_palindrome('racecar'))

bool isPalindrome(string s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s[left] != s[right]) return false;
        left++;
        right--;
    }
    return true;
}

static boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
    while (left < right) {
        if (s.charAt(left) != s.charAt(right)) return false;
        left++;
        right--;
    }
    return true;
}

Inputstring = 'racecar'

OutputTrue

Example

Run the example step by step

Output

Pattern Matching

A very common string problem is finding a short 'needle' string inside a long 'haystack' string. The naive approach (checking every position) takes O(N * M) time.

KMP uses a prefix table to guarantee O(N + M) matching time. Rabin-Karp uses rolling hashes and is commonly O(N + M) on average with a good hash, but hash collisions can make its worst case O(NM).

Naive matching: O(N * M) time
KMP Algorithm: Uses a prefix table to skip redundant checks
Rabin-Karp: Uses rolling hashes for fast comparison

Common mistakes

The most common mistake is ignoring character encodings. If your code assumes 1 byte equals 1 character (ASCII), it will break when encountering multi-byte Unicode emojis or symbols.

Another pitfall is using string slicing (string[1:]) inside a loop. Since slicing creates a new string copy, it quietly turns O(N) algorithms into O(N²) algorithms.

Assuming all characters are exactly 1 byte
Using O(N) string slicing inside recursive functions
Accidental quadratic time from concatenation