String Algorithms in Python: Essential Patterns and Techniques
Counter ignores letter order, so “listen” and “silent” produce identical tallies.

String Algorithms in Python: Essential Patterns and Techniques

String Algorithms in Python: Part of the Data Structures and Algorithms with Python series

You get a string problem in an interview. It looks easy. You write a loop, it passes the sample test, and then it times out on a long input. Or it works, but you cannot explain why it is slow.

This happens a lot, and it usually comes from one gap: not knowing how Python strings really work.

In this guide, you will learn string algorithms in Python the practical way. First, we look at how strings behave and what their operations cost. Then we learn four patterns that solve most string problems. Finally, we apply them to six classic problems and finish with an introduction to KMP.

This article continues from Prefix Sum in Python. There, we answered range queries on arrays. A string is just an array of characters, so those ideas carry over directly.

All the code in this article, with tests, is in the string algorithms GitHub repository. Clone it and run every example as you read.

Python version: I ran every example and the tests in this article on Python 3.12. The code uses features from Python 3.10 and newer, and itertools.batched needs 3.12. Each newer feature is marked where it appears.

In simple terms: A string algorithm is a step-by-step method for searching, comparing, counting, or transforming text. In Python, most string problems are solved with four patterns: two pointers, a sliding window, character counting with a dictionary, and prefix-based preprocessing. Strings are immutable in Python, so how you build them affects speed.

What Are String Algorithms?

String algorithms are step-by-step methods for searching, comparing, counting, and transforming text. In Python, most of them are built from four patterns: two pointers, a sliding window, character counting with a dictionary, and prefix counts.

A string algorithm solves a problem where the input is text. The problems look different, but they ask a few kinds of questions:

  • Is it the same? Palindromes and anagrams.
  • Where is it? Finding a word inside a document.
  • How many? Counting characters, words, or repeated parts.
  • What is the longest or shortest? Longest substring with a rule.

Think of a librarian checking a shelf of books. She might check if two titles match, find one title, count how many start with “A”, or find the longest run of books by one author. Each task needs a different method. Doing it the slow way means pulling every book off the shelf each time.

String algorithms are the faster methods. They avoid repeated work.

How Strings Work in Python

A Python str is a sequence of Unicode characters. You can index it, slice it, and loop over it like a list.

text = 'python'

print(text[0])      # p
print(text[-1])     # n
print(text[1:4])    # yth
print(len(text))    # 6

for ch in text:
    print(ch, ord(ch))  # character and its Unicode code point

Three facts matter for algorithms:

  1. Indexing is fast. text[i] takes constant time.
  2. Slicing makes a copy. text[1:4] builds a new string. The cost grows with the slice length.
  3. len() counts code points, not what a person sees as a character. Most of the time they match. Emoji and accented letters built from combining marks can break that assumption.
print(len('cafe'))        # 4
print(len('cafe\u0301'))  # 5, an 'e' plus a combining accent

For interview problems you can usually assume simple characters. For real products, such as names or chat messages, remember this edge case.

String Immutability and Its Performance Implications

Strings in Python are immutable. You cannot change a character in place.

text = 'hello'
text[0] = 'H'   # TypeError: 'str' object does not support item assignment

Imagine a printed page. If you spot a typo, you cannot erase it. You reprint the whole page. Python does the same. Every “change” creates a new string.

This is why one habit slows down many beginner solutions: building a string with += inside a loop.

# Slow pattern: may copy the growing string on every step
def build_slow(parts):
    result = ''
    for part in parts:
        result += part
    return result

# Better: collect pieces, join once
def build_fast(parts):
    return ''.join(parts)

In theory, the first version copies the string again and again. For n pieces, the total work can grow toward O(n²). CPython sometimes optimizes += behind the scenes, but the language does not promise this, and it fails in other implementations. So do not rely on it.

why-string-concat-is-slow-vs-join-1024x692 String Algorithms in Python: Essential Patterns and Techniques
Building a string with += copies it again at every step. Collecting pieces and calling join() copies each character once.

Rule of thumb: when you build a string piece by piece, append to a list and call ''.join() once at the end. It does the work in one pass, so the cost is linear in the total length.

The same idea applies when you need to change characters. Convert to a list, edit, then join:

chars = list('hello')
chars[0] = 'H'
print(''.join(chars))   # Hello

Common String Operations and Their Complexity

Let n be the length of the string and k the length of a slice or the other string.

OperationExampleTimeNotes
Lengthlen(s)O(1)Stored with the string
Indexs[i]O(1)Returns a 1-character string
Slices[a:b]O(k)Copies k characters
Concatenates + tO(n + k)Creates a new string
Equalitys == tO(min(n, k)) worst caseStops at the first difference
Membershipt in sO(n·k) worst caseSee note below
Join''.join(parts)O(total length)One pass
Splits.split()O(n)Creates a list of new strings
Reverses[::-1]O(n)Creates a new string
Counts.count(t)O(n·k) worst caseNon-overlapping matches

A note on in and find. CPython has improved its substring search over the years. Newer versions use smarter methods for long patterns. But Python does not guarantee one complexity for all versions. In interviews, say “worst case O(n·k)” unless the question asks about a specific implementation. If you quote a CPython detail in an article or talk, check the release notes first.

Essential String Problem-Solving Patterns

Most string problems are one of four patterns in disguise. Learn to spot them and you stop guessing.

Two Pointers for String Problems

Use two indexes that move toward each other, or in the same direction. This works well when you compare characters from both ends.

A good picture: two people reading a sentence aloud, one from the start and one from the end, meeting in the middle. If every pair of letters matches, the sentence is a palindrome.

We covered this pattern in depth in Two Pointers in Python. Here is the short version for strings:

def is_palindrome(s: str) -> bool:
    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('level'))   # True
print(is_palindrome('python'))  # False

It uses O(n) time and O(1) extra space. No copy of the string is made.

Sliding Window for Substrings

Use a window when the answer is a contiguous piece of the string, and a rule decides whether the piece is valid.

Think of a magnifying glass moving over a line of text. You never re-read the whole line. You only move the glass one step and look at what changed. The full guide is in Sliding Window Technique in Python. We use it below for the longest substring problem.

Hashing and Character Frequency Counting

When the question is “how many of each character?”, use a dictionary. Python gives you collections.Counter, which does the counting for you.

from collections import Counter

print(Counter('banana'))
# Counter({'a': 3, 'n': 2, 'b': 1})

Think of a cashier tallying items at a checkout. Each item adds one to its own tally. Counting n characters takes O(n) time. The space is O(k), where k is the number of distinct characters. For lowercase English letters, k is at most 26, which is constant.

Prefix-Based String Techniques

In the last article, a prefix sum array let us answer range sums in O(1) after O(n) setup. The same trick works on strings. Instead of summing numbers, we count things: vowels, a specific letter, or any property of a character.

Say you build a search feature that shows how many vowels appear in a selected part of a word, again and again. Prefix counts make every query instant.

from itertools import accumulate

def build_vowel_prefix(s: str) -> list[int]:
    is_vowel = (ch.lower() in 'aeiou' for ch in s)
    return list(accumulate(is_vowel, initial=0))

def vowels_in_range(prefix: list[int], left: int, right: int) -> int:
    # inclusive range s[left..right]
    return prefix[right + 1] - prefix[left]

word = 'education'
prefix = build_vowel_prefix(word)
print(prefix)                         # [0, 1, 1, 2, 2, 3, 3, 4, 5, 5]
print(vowels_in_range(prefix, 2, 5))  # 'ucat' -> 2 (u and a)

accumulate(..., initial=0) builds the whole prefix array in one line. The initial=0 value adds the leading zero, so the range formula stays simple.

This is the same prefix idea with a different value added at each step. Note that “prefix” has a second meaning in string problems: the starting part of a string, as in 'pre' is a prefix of 'prefix'. We use that meaning in KMP later.

Common String Problems in Python

Now let us use the patterns. For each problem, we start with the idea, then the code.

Reverse a String

Idea: Read the characters from the end to the start.

s = 'algorithm'

print(s[::-1])                 # mhtirogla
print(''.join(reversed(s)))    # mhtirogla

Both take O(n) time and O(n) space, because the result is a new string. Slicing is shorter. reversed() is more explicit. Pick the one your team finds clearer.

A related problem is reversing the words while keeping each word as is:

sentence = 'the sky is blue'
print(' '.join(sentence.split()[::-1]))   # blue is sky the

Check Whether a String Is a Palindrome

The earlier version only works on clean input. Real input has spaces, punctuation, and mixed case, like 'A man, a plan, a canal: Panama'.

Idea: Use two pointers, but skip characters that are not letters or digits, and compare in lowercase.

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        while left < right and not s[left].isalnum():
            left += 1
        while left < right and not s[right].isalnum():
            right -= 1
        if s[left].casefold() != s[right].casefold():
            return False
        left += 1
        right -= 1
    return True

print(is_palindrome('A man, a plan, a canal: Panama'))  # True
print(is_palindrome('race a car'))                       # False
print(is_palindrome(''))                                 # True

The shortcut version is shorter. It uses casefold(), which compares text more reliably than lower() across languages:

def is_palindrome_short(s: str) -> bool:
    cleaned = [c.casefold() for c in s if c.isalnum()]
    return cleaned == cleaned[::-1]

It uses O(n) extra space, while the pointer version uses O(1). Mention both in an interview and explain the trade-off.

Check Whether Two Strings Are Anagrams

Two words are anagrams when they use the same letters the same number of times. 'listen' and 'silent' are anagrams.

Idea: Count the characters in each string and compare the counts.

from collections import Counter

def is_anagram(a: str, b: str) -> bool:
    return len(a) == len(b) and Counter(a) == Counter(b)

print(is_anagram('listen', 'silent'))   # True
print(is_anagram('rat', 'car'))         # False

The length check is a cheap early exit. Time is O(n), space is O(k).

Sorting also works: sorted(a) == sorted(b). It is shorter, but it costs O(n log n). Counting is faster for long strings.

String Algorithms in Python: Essential Patterns and Techniques
Counter ignores letter order, so “listen” and “silent” produce identical tallies.

Find the First Non-Repeating Character

Think of a queue of people at a ticket counter, and you want the first person whose name nobody else shares.

Idea: Pass 1 counts every character. Pass 2 walks the string in order and returns the first character with a count of 1.

from collections import Counter

def first_non_repeating(s: str) -> int:
    counts = Counter(s)
    return next((i for i, ch in enumerate(s) if counts[ch] == 1), -1)

print(first_non_repeating('leetcode'))   # 0  ('l')
print(first_non_repeating('aabb'))       # -1

Two passes are still O(n) overall. The next() call takes a default value, so it returns -1 when no character is unique. We return the index because a character alone does not tell you where it was.

Find the Longest Substring Without Repeating Characters

This is a very popular interview question. A browser-style example: you scan a stream of keystrokes and want the longest run with no repeated key.

Brute force: Check every substring. That is O(n²) substrings, and checking each takes more time. Too slow.

Insight: When we meet a repeated character, we do not need to restart. We only move the left edge of the window just past the earlier copy.

def longest_unique_substring(s: str) -> int:
    last_seen: dict[str, int] = {}   # character -> most recent index
    left = best = 0
    for right, ch in enumerate(s):
        left = max(left, last_seen.get(ch, -1) + 1)
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(longest_unique_substring('abcabcbb'))  # 3  ('abc')
print(longest_unique_substring('pwwkew'))    # 3  ('wke')
print(longest_unique_substring(''))          # 0

The key line is left = max(left, last_seen.get(ch, -1) + 1). If the character was seen before the window started, max keeps left where it is. Without it, an old position would drag the window backward. Using dict.get with a default also removes the separate in check.

Time: O(n), since right visits each position once and left only moves forward. Space: O(k) for the dictionary.

Sliding-Window-on-abcabcbb-879x1024 String Algorithms in Python: Essential Patterns and Techniques
The right pointer moves one step each time. The left pointer jumps forward past a repeated character and never moves back.

Find a Pattern Within a String

You want every position where a word appears inside a larger text, like “Ctrl+F” in an editor.

Brute force: Try every starting position.

def naive_search(text: str, pattern: str) -> list[int]:
    n, m = len(text), len(pattern)
    if m == 0:
        return []
    matches = []
    for i in range(n - m + 1):
        if text.startswith(pattern, i):
            matches.append(i)
    return matches

print(naive_search('ababcabab', 'abab'))   # [0, 5]

We use startswith(pattern, i) instead of text[i:i+m] == pattern. It compares in place and avoids creating a slice at every position.

Time is O(n·m) in the worst case, for example text 'aaaaaaaa' and pattern 'aaab'. For most real text it is much faster. If you need worst-case guarantees, read the KMP section below.

Built-In Python String Methods vs Custom Algorithms

A good developer does not rewrite what Python already does well. Built-in methods are implemented in C and are usually faster than a Python loop.

TaskBuilt-inWrite your own when…
Find a substrings.find(t), t in sYou need all overlapping matches or a guaranteed worst case
Count a substrings.count(t)You need overlapping counts
Count charactersCounter(s)You need a custom rule per character
Reverses[::-1]You are asked to do it in place, in an interview
Split into wordss.split()The delimiter rules are unusual
Check prefix or suffixs.startswith(x), s.endswith(x)Almost never

In an interview, the interviewer usually wants to see the algorithm, so ask: “May I use built-ins here?” At work, the built-in is the right choice most of the time. Write your own only when you know why.

Modern Python Shortcuts for String Problems

Newer Python versions removed a lot of boilerplate. These shortcuts make string code shorter and safer. The comments show which version added each one.

from collections import Counter
from itertools import batched, pairwise   # batched needs Python 3.12+

url = 'https://emitechlogic.com/blog'
print(url.removeprefix('https://'))                          # emitechlogic.com/blog  (3.9+)
print('report.csv'.removesuffix('.csv'))                     # report  (3.9+)
print('Straße'.casefold() == 'STRASSE'.casefold())           # True  (Unicode-safe compare)
print(sum(a == b for a, b in pairwise('aabbbc')))            # 3 equal neighbours  (3.10+)
print(Counter('banana').total())                             # 6  (3.10+)
print([''.join(c) for c in batched('abcdefg', 3)])           # ['abc', 'def', 'g']  (3.12+)

removeprefix() is safer than lstrip(). The strip family removes a set of characters, not a prefix. Here is what that does to a real URL:

print('https://tech.com'.lstrip('https://'))        # ech.com  (the 't' was eaten)
print('https://tech.com'.removeprefix('https://'))   # tech.com

Here is a shortcut for finding every match, including overlapping ones. It uses the walrus operator (:=), which assigns and tests in one step:

from collections.abc import Iterator

def find_all(text: str, pattern: str) -> Iterator[int]:
    if not pattern:
        return
    start = 0
    while (index := text.find(pattern, start)) != -1:
        yield index
        start = index + 1

print(list(find_all('aaaa', 'aa')))   # [0, 1, 2]

Each search starts one step after the last match, so overlaps are found. It is a generator, so it never builds the whole result list unless you ask for one. Because find runs in C, this is often the practical choice in real code.

Introduction to KMP and Other String-Matching Algorithms

KMP (Knuth-Morris-Pratt) is a string-matching algorithm that finds a pattern inside a text in O(n + m) time. It builds a table from the pattern first, so a failed match never moves the text pointer backward.

The naive search wastes work. When a match fails halfway, it forgets everything it learned and starts again one step to the right.

The Knuth-Morris-Pratt (KMP) algorithm remembers. It first studies the pattern and builds a table. The table says: “if the match fails here, how much of the pattern can I still keep?”

Imagine reading the word abab and failing at the next letter. You already matched ab at the end, and ab is also how the pattern starts. So you do not need to go back to zero. You continue from ab.

KMP-LPS-Table-for-abab-859x1024 String Algorithms in Python: Essential Patterns and Techniques
The LPS table for “abab”. At index 3, the prefix “ab” matches the suffix “ab”, so the value is 2.

The table is called the LPS array (longest proper prefix that is also a suffix).

def build_lps(pattern: str) -> list[int]:
    lps = [0] * len(pattern)
    length = 0
    for i in range(1, len(pattern)):
        while length > 0 and pattern[i] != pattern[length]:
            length = lps[length - 1]
        if pattern[i] == pattern[length]:
            length += 1
        lps[i] = length
    return lps

def kmp_search(text: str, pattern: str) -> list[int]:
    if not pattern:
        return []
    lps = build_lps(pattern)
    matches = []
    j = 0   # how many pattern characters are matched so far
    for i, ch in enumerate(text):
        while j > 0 and ch != pattern[j]:
            j = lps[j - 1]
        if ch == pattern[j]:
            j += 1
        if j == len(pattern):
            matches.append(i - j + 1)
            j = lps[j - 1]
    return matches

print(build_lps('abab'))                 # [0, 0, 1, 2]
print(kmp_search('ababcabab', 'abab'))   # [0, 5]

The text pointer i never moves backward. That gives O(n + m) time and O(m) space for the table. It also finds overlapping matches, like 'abab' inside 'ababab'.

Other algorithms worth knowing by name:

  • Rabin-Karp: uses a rolling hash to compare windows. Good for searching many patterns.
  • Z-algorithm: computes how much each position matches the start of the string.
  • Trie: stores many words by their shared prefixes. Good for autocomplete.

Rabin-Karp gets a closer look next. The Z-algorithm, Boyer-Moore and tries each deserve a guide of their own.

Rabin-Karp: Searching With a Rolling Hash

Rabin-Karp is a string-matching algorithm that uses a rolling hash to compare each window of the text with the pattern. It runs in O(n + m) time on average, and it checks every hash match to rule out collisions.

Rabin-Karp compares numbers instead of letters. It turns each window of the text into a hash, then slides the window one step at a time. Updating the hash takes constant time, so you never re-read the whole window.

Think of a barcode scanner at a shop. It does not read every product name. It reads a short code, and only checks the full name when the codes match.

def rabin_karp(text: str, pattern: str, base: int = 256, mod: int = 1_000_000_007) -> list[int]:
    n, m = len(text), len(pattern)
    if m == 0 or m > n:
        return []
    high = pow(base, m - 1, mod)   # weight of the leftmost character
    p_hash = t_hash = 0
    for i in range(m):
        p_hash = (p_hash * base + ord(pattern[i])) % mod
        t_hash = (t_hash * base + ord(text[i])) % mod
    matches = []
    for i in range(n - m + 1):
        if p_hash == t_hash and text.startswith(pattern, i):
            matches.append(i)
        if i < n - m:   # slide the window one step to the right
            t_hash = ((t_hash - ord(text[i]) * high) * base + ord(text[i + m])) % mod
    return matches

print(rabin_karp('ababcabab', 'abab'))   # [0, 5]

A matching hash does not prove a match, because two different windows can share a hash. So we confirm with startswith. Equal strings always have equal hashes, so we never miss a real match.

The average time is O(n + m). The worst case is O(n·m), when many windows collide. Rabin-Karp shines when you search for many patterns of the same length at once: store their hashes in a set and check each window against it.

KMP vs Rabin-Karp vs Python’s in

MethodTimeExtra spaceBest for
in / findTreat as O(n·m) worst case; fast in practiceO(1)Everyday search
Naive loopO(n·m)O(1)Learning, tiny inputs
KMPO(n + m)O(m)A guaranteed worst-case bound
Rabin-KarpO(n + m) average, O(n·m) worstO(1)Many patterns of equal length
Boyer-MooreOften skips characters; worst case depends on the variantO(alphabet size)Long patterns in large texts

Time and Space Complexity of String Algorithms

Most string patterns run in O(n) time, because two pointers, a sliding window, and character counting each pass over the string once. Naive pattern search takes O(n·m) in the worst case, and KMP improves that to O(n + m).

ProblemApproachTimeExtra space
Reverse a stringSlicingO(n)O(n)
Palindrome checkTwo pointersO(n)O(1)
Anagram checkCounterO(n)O(k)
First non-repeating characterTwo passesO(n)O(k)
Longest unique substringSliding windowO(n)O(k)
Pattern searchNaiveO(n·m) worstO(1)
Pattern searchKMPO(n + m)O(m)
Vowel range queriesPrefix countsO(n) build, O(1) per queryO(n)

Here k is the number of distinct characters. For lowercase letters it is at most 26. For full Unicode text it can be much larger, so do not always treat it as a constant.

Also remember that slicing, join, and split have their own costs. A loop that looks like O(n) can become O(n²) if each step slices or concatenates.

How to Recognize the Right String Pattern

Read the problem and look for these clues:

Which-String-Pattern-Should-You-Use-834x1024 String Algorithms in Python: Essential Patterns and Techniques
Answer the questions from the top. The first “Yes” points to the technique to try.
If the problem says…Think of…
Palindrome, compare from both ends, in placeTwo pointers
Longest or shortest substring with a ruleSliding window
Anagram, frequency, “how many of each”, duplicatesHash map or Counter
Many queries on the same string, count in a rangePrefix counts
Find one string inside anotherfind, then KMP if worst case matters
Many words sharing beginningsTrie

A substring is contiguous. A subsequence is not. That one word changes the technique, so read it carefully.

Common String Algorithm Mistakes

  1. Using += in a big loop. Collect pieces in a list and use ''.join().
  2. Slicing inside a loop without noticing. Each slice is a copy. Prefer indexes or startswith(x, i).
  3. Off-by-one errors. s[a:b] excludes b. Prefix arrays need right + 1.
  4. Forgetting the empty string. Test '' before you submit.
  5. Ignoring case and punctuation. Ask whether 'A' equals 'a'.
  6. Forgetting the left = max(...) check in a sliding window. Old positions outside the window must be ignored.
  7. Assuming only ASCII. Ask what the character set is. It changes the space analysis.
  8. Trying to edit a string in place. Convert to a list first.

Practice Problems With Solutions

1. Is Subsequence. Given s and t, check whether s can be made by deleting some characters from t without reordering. Pattern: two pointers.

def is_subsequence(s: str, t: str) -> bool:
    i = 0
    for ch in t:
        if i < len(s) and ch == s[i]:
            i += 1
    return i == len(s)

print(is_subsequence('ace', 'abcde'))   # True
print(is_subsequence('aec', 'abcde'))   # False

Time O(len(t)), space O(1).

Shortcut: an iterator remembers its position, so each in check keeps scanning forward through t.

def is_subsequence_short(s: str, t: str) -> bool:
    it = iter(t)
    return all(ch in it for ch in s)

It is compact but harder to read. Use the loop first, and show this one if the interviewer asks for something shorter.

2. Group Anagrams. Group words that are anagrams of each other. Pattern: hashing with a canonical key.

from collections import defaultdict

def group_anagrams(words: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for word in words:
        groups[''.join(sorted(word))].append(word)
    return list(groups.values())

print(group_anagrams(['eat', 'tea', 'tan', 'ate', 'nat', 'bat']))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Sorted letters act as a shared fingerprint. Time is O(N · L log L) for N words of length up to L.

3. Longest Common Prefix. Find the longest starting part shared by all strings. Pattern: shrink the candidate.

def longest_common_prefix(strs: list[str]) -> str:
    if not strs:
        return ''
    prefix = strs[0]
    for word in strs[1:]:
        while not word.startswith(prefix):
            prefix = prefix[:-1]
    return prefix

print(longest_common_prefix(['flower', 'flow', 'flight']))   # fl
print(longest_common_prefix(['dog', 'racecar']))             # (empty string)

Time is O(total characters) in the worst case. The loop always ends, because an empty prefix matches every string.

Try it yourself: write a function that counts how many times each vowel appears in any range of a string, using the prefix idea from above. Hint: keep one prefix array per vowel.

Test Your String Functions

Passing the sample inputs proves very little. A better habit is to compare your fast solution with a slow, obvious one on many random inputs. If they ever disagree, you have found a bug.

Save the functions from this article in string_algorithms.py, then add this test_strings.py:

import random

from string_algorithms import (
    kmp_search,
    longest_unique_substring,
    naive_search,
    rabin_karp,
)

def brute_longest_unique(s: str) -> int:
    best = 0
    for i in range(len(s)):
        seen = set()
        for j in range(i, len(s)):
            if s[j] in seen:
                break
            seen.add(s[j])
            best = max(best, j - i + 1)
    return best

def test_longest_unique_matches_brute_force():
    rng = random.Random(7)
    for _ in range(500):
        s = ''.join(rng.choices('abc', k=rng.randint(0, 12)))
        assert longest_unique_substring(s) == brute_longest_unique(s)

def test_search_algorithms_agree():
    rng = random.Random(11)
    for _ in range(500):
        text = ''.join(rng.choices('ab', k=rng.randint(0, 15)))
        pattern = ''.join(rng.choices('ab', k=rng.randint(1, 4)))
        expected = naive_search(text, pattern)
        assert kmp_search(text, pattern) == expected
        assert rabin_karp(text, pattern) == expected

Run pytest. The tiny alphabet is on purpose. It forces repeated characters, overlapping matches, and empty or short inputs, which is where string bugs hide.

Frequently Asked Questions

  1. Why are strings immutable in Python?

    Immutability makes strings safe to share, and it lets Python cache their hash values. That is why strings work well as dictionary keys. The cost is that every change creates a new string.

  2. Is s[::-1] the fastest way to reverse a string?

    It is usually the shortest and fast in practice, because the work happens in C. It still takes O(n) time and space. For in-place reversal, you need a mutable type such as a list.

  3. What is the time complexity of in for strings?

    Treat it as O(n·m) in the worst case in interviews. Real CPython performance is often better, but Python does not promise a single bound.

  4. When should I use Counter instead of a normal dictionary?

    Use Counter whenever you are counting. It is shorter, handles missing keys, and supports comparison with ==. Use a normal dict when you store something other than counts, such as indexes.

  5. Do I need to learn KMP for interviews?

    Many interviews accept find or in for simple search. KMP matters when the question asks for worst-case guarantees, or when you are applying for roles that involve text processing. Knowing the idea is more useful than memorizing the code.

  6. Is KMP faster than Python’s in operator?

    Usually not. in and find run in C, so they tend to beat a KMP loop written in Python. Use KMP when you need a guaranteed O(n + m) bound, when you are learning how matching works, or when you must write the logic in a language without a strong built-in search.

  7. How do I choose between a sliding window and a hash map?

    Use a sliding window when the answer is a contiguous piece with a rule. Use a hash map to count or look things up. Many problems, like the longest unique substring, use both.

Conclusion

String problems feel hard because they hide simple patterns. Python strings are immutable, so build with join. Remember that slices copy. Then match the problem to one of four patterns: two pointers, sliding window, character counting, or prefix counts. When you need worst-case search speed, KMP is your next step.

If you want the full path, follow the complete DSA with Python roadmap.

Next, we move from reading data to changing it. In Difference Arrays in Python, you will see how to apply thousands of range updates without touching every element, the mirror image of the prefix sum idea.

External Resources and Further Reading

These sources back up the technical claims in this guide. Read them when you want the official detail.

Official Python documentation

Python Enhancement Proposals

Algorithm references

About the author Emmimal P Alexander is an AI Engineer and author dedicated to building applied AI systems that perform reliably in real-world production environments. She founded EmiTechLogic, an educational platform where she writes about neural networks, deep learning, large language models, and agentic AI—with a strong emphasis on practical engineering over idealized theory. Her background includes a BCA in computer applications, an MBA in business administration, and years of independent research and hands-on development in AI. She specializes in bridging theory to production-grade systems, tackling challenges like reliability, accountability, governance, AI hallucination, and well-defined decision boundaries. Emmimal is the author of Neural Networks and Deep Learning with Python: A Practical Approach and Agentic AI for Executives, where she explores not just models but the full systems around them—including failure modes and organizational risks. Through her writing, she prioritizes clarity over hype and sustainable impact over demos, helping practitioners and leaders understand how AI truly behaves when deployed. Check out her books on Amazon: https://www.amazon.com/stores/Emmimal-P-Alexander/author/B0DNGBTBRX

Leave a Reply

Your email address will not be published. Required fields are marked *

  • Rating