Skip to content

02_strings

Directory actions

More options

Directory actions

More options

Latest commit

 

History

History

02_strings

Folders and files

README.md

layout default
title Strings
nav_order 11
has_children true
permalink /02_strings/

📝 Strings

Immutable sequences of characters - fundamental for text processing

Difficulty Subtopics Problems

Immutable sequences of characters - fundamental for text processing

⬅️ Previous: Arrays | 🏠 Home | Next: Linked Lists ➡️

📊 Visual Overview

String Problem Given

String Problem Given

📊 Visual Overview

Strings Overview

Strings Overview

🎯 At a Glance
In one line Immutable sequences of characters - fundamental for text processing
Difficulty Easy to Hard
Subtopics 4
Problems 50+

How to use this page: Start with the visual overview, scan At a Glance, then work through theory → walkthroughs → code.

📂 Subtopics Navigation

# Topic Problems Link
1 Basic String 10+ 📖 Go →
2 Anagram Problems 10+ 📖 Go →
3 Palindrome 12+ 📖 Go →
4 Subsequence 10+ 📖 Go →

📐 Mathematical Foundation

1️⃣ String Representation

A string $S$ of length $n$ over alphabet $\Sigma$:

$$S = s_0 s_1 s_2 \cdots s_{n-1} \quad \text{where } s_i \in \Sigma$$

ASCII Encoding:

$$\text{char value} = \text{ord}(c) \in [0, 127]$$

Memory:

$$\text{Address}(S[i]) = \text{Base} + i \times \text{sizeof(char)}$$

2️⃣ Substring Count

Number of substrings of length $k$ in string of length $n$:

$$n - k + 1$$

Total substrings (including empty):

$$\boxed{\frac{n(n+1)}{2} + 1}$$

Proof:

Substrings starting at position 0: n choices Substrings starting at position 1: n-1 choices ... Substrings starting at position n-1: 1 choice

Total = n + (n-1) + ... + 1 = n(n+1)/2 Plus 1 for empty string = n(n+1)/2 + 1 ∎

3️⃣ Anagram Condition

Theorem: Strings $S$ and $T$ are anagrams if and only if:

$$\boxed{\forall c \in \Sigma: \text{count}_S(c) = \text{count}_T(c)}$$

Equivalent Conditions:

  1. $\text{sorted}(S) = \text{sorted}(T)$

  2. $\vec{f}(S) = \vec{f}(T)$ (frequency vectors equal)

  3. $|S| = |T|$ and $S$ is a permutation of $T$

Frequency Vector (for lowercase letters):

$$\vec{f}(S) = [\text{count}_S('a'), \text{count}_S('b'), \ldots, \text{count}_S('z')] \in \mathbb{Z}^{26}$$

Proof:

$$S \sim T \iff \vec{f}(S) = \vec{f}(T) \iff \text{sorted}(S) = \text{sorted}(T) ; \blacksquare$$

4️⃣ Palindrome Mathematics

Definition: String $S[0..n-1]$ is a palindrome if:

$$\boxed{S[i] = S[n-1-i] \quad \forall i \in [0, \lfloor n/2 \rfloor]}$$

Palindrome Centers Formula:

$$\text{Total centers} = 2n - 1$$

  • Odd length palindromes: $n$ centers at indices $0, 1, \ldots, n-1$

  • Even length palindromes: $n-1$ centers between indices

Expansion Formula:

For center at position $c$ (using $2n-1$ indexing):

$$\text{left} = \left\lfloor \frac{c}{2} \right\rfloor, \quad \text{right} = \left\lfloor \frac{c}{2} \right\rfloor + (c \bmod 2)$$

Proof of Center Count:

5️⃣ Edit Distance (Levenshtein)

Recurrence Relation:

$$\boxed{dp[i][j] = \begin{cases} i & \text{if } j = 0 \\ j & \text{if } i = 0 \\ dp[i-1][j-1] & \text{if } S[i-1] = T[j-1] \\ 1 + \min \begin{cases} dp[i-1][j] & \text{(delete)} \\ dp[i][j-1] & \text{(insert)} \\ dp[i-1][j-1] & \text{(replace)} \end{cases} & \text{otherwise} \end{cases}}$$

Operations Cost:

  • Delete from $S$: $dp[i-1][j] + 1$

  • Insert into $S$: $dp[i][j-1] + 1$

  • Replace in $S$: $dp[i-1][j-1] + 1$

Optimal Substructure Proof:

Let $E(i,j)$ = edit distance between $S[0..i-1]$ and $T[0..j-1]$

Case 1: If $S[i-1] = T[j-1]$, no operation needed:

$$E(i,j) = E(i-1, j-1)$$

Case 2: If $S[i-1] \neq T[j-1]$, try all operations:

  • Delete $S[i-1]$: match $S[0..i-2]$ with $T[0..j-1]$ → $E(i-1,j) + 1$

  • Insert $T[j-1]$: match $S[0..i-1]$ with $T[0..j-2]$ → $E(i,j-1) + 1$

  • Replace $S[i-1]$ with $T[j-1]$: match $S[0..i-2]$ with $T[0..j-2]$ → $E(i-1,j-1) + 1$

Take minimum → optimal ∎

6️⃣ Longest Common Subsequence (LCS)

State Definition:

$$dp[i][j] = \text{LCS length of } S[0..i-1] \text{ and } T[0..j-1]$$

Recurrence:

$$\boxed{dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & \text{if } S[i-1] = T[j-1] \\ \max(dp[i-1][j], dp[i][j-1]) & \text{otherwise} \end{cases}}$$

Base Case: $dp[0][j] = dp[i][0] = 0$

Properties:

$$\text{LCS}(S, \text{reverse}(S)) = \text{Longest Palindromic Subsequence}$$

Correctness Proof:

Optimal Substructure:

If $S[i-1] = T[j-1]$, they must appear in LCS (greedy is optimal):

$$\text{LCS}(S[0..i-1], T[0..j-1]) = \text{LCS}(S[0..i-2], T[0..j-2]) + 1$$

If $S[i-1] \neq T[j-1]$, one must be excluded:

$$\text{LCS} = \max(\text{LCS}(S[0..i-2], T[0..j-1]), \text{LCS}(S[0..i-1], T[0..j-2]))$$

By induction on string lengths, DP computes optimal solution ∎

7️⃣ String Hashing (Polynomial Rolling Hash)

Hash Function:

$$\boxed{H(S) = \sum_{i=0}^{n-1} s_i \cdot p^i \mod m}$$

Where:

  • $p$ is a prime (typically 31 for lowercase, 53 for mixed case)

  • $m$ is a large prime ($10^9 + 7$ or $10^9 + 9$)

Rolling Update (add character on right):

$$H(S + c) = (H(S) + c \cdot p^n) \mod m$$

Rolling Update (remove character from left):

$$H(S[1..n]) = \frac{H(S[0..n]) - s_0}{p} \mod m$$

Collision Probability:

For two different strings:

$$P(\text{collision}) \approx \frac{1}{m}$$

Example Calculation:

For string "abc" with $p=31$, $m=10^9+7$:

$$H(\text{"abc"}) = (97 \cdot 31^0 + 98 \cdot 31^1 + 99 \cdot 31^2) \bmod (10^9+7) = (97 + 3038 + 95139) \bmod (10^9+7) = 98274$$

8️⃣ KMP Algorithm - Failure Function

Failure Function: $\pi[i]$ = length of longest proper prefix of $P[0..i]$ that is also a suffix

Recurrence:

$$\pi[i] = \begin{cases} 0 & \text{if } i = 0 \\ \pi[\pi[i-1]] & \text{if } P[i] \neq P[\pi[i-1]] \text{ (backtrack)} \\ \pi[i-1] + 1 & \text{if } P[i] = P[\pi[i-1]] \end{cases}$$

Time Complexity Proof:

Let $k$ = value of $\pi[i]$ at any point.

  • Each successful match: $k$ increases by 1

  • Each mismatch: $k$ decreases (follows $\pi$ links)

  • $k$ can increase at most $n$ times

  • $k$ can decrease at most $n$ times (can't go negative)

Total operations: $O(n)$ ∎

Matching Time: $O(n + m)$ where $n = |S|$, $m = |P|$

🚀 Getting Started

Prerequisites

  • Understanding of arrays and hash maps

  • Familiarity with two pointers technique

  • Basic knowledge of dynamic programming

Study Strategy

Week 1-2: Basic operations + Anagrams
Week 3-4: Palindromes + Sliding window
Week 5-6: DP problems (LCS, Edit distance)

⚡ Complexity Reference

Operation Time Python Java Notes
Access s[i] O(1) ✓ ✓ Direct indexing
Length O(1) ✓ ✓ Cached
Slice s[i:j] O(j-i) ✓ - Creates new string
Concatenate O(n+m) ✓ ✓ New string created
Find substring O(nm) ✓ ✓ Naive; KMP is O(n+m)
Compare O(n) ✓ ✓ Character by character

String Building Optimization

Approach Time When to Use
Repeated += O(n²) ❌ Never
StringBuilder/List O(n) ✅ Multiple concatenations
''.join() O(n) ✅ Combining list of strings

🎯 Must-Solve Problems (Top 15)

# Problem Category Difficulty Why Important
1 Valid Anagram Frequency 🟢 Easy Foundation pattern
2 Valid Palindrome Two Pointers 🟢 Easy Most common
3 Longest Substring Without Repeating Sliding Window 🟡 Medium Top interview
4 Longest Palindromic Substring Expand Center 🟡 Medium Classic
5 Group Anagrams Hash + Sort 🟡 Medium Real-world
6 Find All Anagrams Sliding Window 🟡 Medium Window pattern
7 Palindromic Substrings Expand Center 🟡 Medium Counting
8 Longest Common Subsequence DP 🟡 Medium DP foundation
9 Reverse Words Two Pointers 🟡 Medium Parsing
10 Palindrome Partitioning Backtracking 🟡 Medium Combination
11 Minimum Window Substring Sliding Window 🔴 Hard Hardest window
12 Edit Distance DP 🔴 Hard Classic DP
13 Regular Expression Matching DP 🔴 Hard Pattern matching
14 Distinct Subsequences DP 🔴 Hard Counting DP
15 Longest Valid Parentheses Stack/DP 🔴 Hard Multiple approaches

🏆 LeetCode Problems (Complete List)

🟢 Easy

# Problem Technique Time Space
14 Longest Common Prefix Vertical Scan O(mn) O(1)
28 Find Index of First Occurrence KMP O(n+m) O(m)
125 Valid Palindrome Two Pointers O(n) O(1)
242 Valid Anagram Counter O(n) O(1)
344 Reverse String Two Pointers O(n) O(1)
387 First Unique Character Counter O(n) O(1)
392 Is Subsequence Two Pointers O(n) O(1)

🟡 Medium

# Problem Technique Time Space
3 Longest Substring Without Repeating Sliding Window O(n) O(k)
5 Longest Palindromic Substring Expand Center O(n²) O(1)
22 Generate Parentheses Backtracking O(4ⁿ/√n) O(n)
49 Group Anagrams Hash + Sort O(nk log k) O(nk)
131 Palindrome Partitioning Backtracking O(n⋅2ⁿ) O(n)
151 Reverse Words in a String Two Pointers O(n) O(n)
438 Find All Anagrams Sliding Window O(n) O(1)
647 Palindromic Substrings Expand Center O(n²) O(1)
1143 Longest Common Subsequence DP O(mn) O(mn)

🔴 Hard

# Problem Technique Time Space
10 Regular Expression Matching DP O(mn) O(mn)
32 Longest Valid Parentheses Stack/DP O(n) O(n)
72 Edit Distance DP O(mn) O(mn)
76 Minimum Window Substring Sliding Window O(n) O(k)
115 Distinct Subsequences DP O(mn) O(mn)

💡 Key Insights & Pro Tips

🎯 String Immutability
Strings are immutable in Python/Java. Use StringBuilder or list for O(n) instead of O(n²) concatenation.

⚡ Fixed Alphabet Optimization
For 26 lowercase letters, use int[26] instead of HashMap for O(1) space and better constants.

🔄 Palindrome Centers
Always remember 2n-1 centers. This is the key to O(n²) palindrome problems.

📊 Sliding Window Template

expand right → add to window
while (invalid) → contract left
update answer

🔍 DP on Strings Pattern
dp[i][j] usually means "answer for S[0..i-1] and T[0..j-1]". Match chars or skip, take optimal.

🧮 Quick Pattern Reference

If Problem Says... Think... Examples
"valid palindrome" Two Pointers #125, #680
"anagram" or "permutation" Character Frequency #242, #49, #567
"longest substring without..." Sliding Window + Set #3
"find all anagrams" Sliding Window + Frequency #438
"palindromic substrings" Expand Around Center #5, #647
"partition" Backtracking + Palindrome Check #131
"longest common subsequence" 2D DP #1143
"edit distance" 2D DP #72
"minimum window" Sliding Window #76
"pattern matching" KMP or DP #28, #10

🎓 Pattern Recognition Flowchart

🎓 Pattern Recognition Flowchart

📚 References & Learning Resources

📖 Books & Courses

Resource Description Link
CLRS Chapter 32 String matching algorithms MIT Press
Algorithms on Strings Comprehensive textbook Cambridge
Competitive Programming 3 Chapter 6: String processing Book
Algorithms 4th Edition Sedgewick & Wayne Book Site

🌐 Online Tutorials

Resource Description Link
CP-Algorithms String algorithms encyclopedia Strings
GeeksforGeeks String tutorials & problems Strings
LeetCode Explore String learning path Card
HackerEarth String algorithms tutorial Tutorial

📺 Video Resources

Resource Topic Link
NeetCode String patterns playlist YouTube
Abdul Bari KMP algorithm explained YouTube
Back To Back SWE String problems series YouTube
William Fiset String algorithms YouTube
MIT OCW 6.006 String matching lecture MIT
Tushar Roy DP on strings YouTube

📝 Practice Platforms

Platform Focus Link
LeetCode Interview problems String Tag
HackerRank String manipulation Practice
Codeforces Competitive programming String Problems
CodeChef Monthly contests Strings
AtCoder Japanese contests Problems

🔬 Advanced Topics

Topic Description Link
KMP Algorithm O(n+m) pattern matching Wikipedia
Rabin-Karp Rolling hash technique GeeksforGeeks
Manacher's Algorithm O(n) longest palindrome CP-Algorithms
Aho-Corasick Multiple pattern matching Wikipedia
Suffix Array Advanced string structure CP-Algorithms
Suffix Tree Generalized suffix structure GeeksforGeeks
Z-Algorithm String matching in O(n) CP-Algorithms
Boyer-Moore Fast pattern matching Wikipedia

🎯 Problem Collections

Collection Focus Link
NeetCode 150 Curated interview problems Strings
Blind 75 Essential coding problems List
Grind 75 Week-by-week preparation Guide
Striver's SDE Sheet Must-do problems Sheet
LeetCode Patterns 14 patterns guide Sean Prashad

📊 Visualization Tools

Tool Purpose Link
Regex101 Regular expressions tester Website
VisuAlgo String algorithms visualization Suffix Array
Algorithm Visualizer Step-by-step execution Website
String Matching Viz Pattern matching demo Tool

🏆 Competition Resources

Resource Topic Link
USACO Guide String algorithms guide Guide
TopCoder Tutorials & editorials Articles
Codeforces EDU Educational courses Course
CSES Problem Set Finnish platform Strings

📚 Research Papers

Paper Topic Link
Knuth-Morris-Pratt (1977) Original KMP paper Paper
Manacher (1975) Linear time palindromes Paper
Levenshtein (1966) Edit distance Paper

🎖️ Interview Success Tips

Common Mistakes to Avoid

❌ Don't:

  • Concatenate strings in loops without StringBuilder

  • Forget about empty string edge case

  • Ignore case sensitivity requirements

  • Use nested loops when sliding window works

  • Forget to handle Unicode characters

✅ Do:

  • Use StringBuilder/list for multiple concatenations

  • Test with edge cases: empty, single char, all same

  • Clarify case sensitivity and special characters

  • Recognize sliding window patterns early

  • Consider both ASCII and Unicode

Optimization Checklist

  • Can I use character array instead of HashMap?
  • Is sliding window applicable?
  • Should I use expand-around-center for palindromes?
  • Is this a DP problem? (LCS, edit distance patterns)
  • Can rolling hash optimize substring search?
  • Am I avoiding O(n²) string concatenation?

🌟 Motivational Corner

"Strings are everywhere - from DNA sequences to search engines. Master them, and you master text processing."

Progress Tracker:

  • 🥉 Bronze: Solve 20 string problems

  • 🥈 Silver: Solve 50 string problems

  • 🥇 Gold: Solve 100 string problems

  • 💎 Platinum: Can explain KMP and solve hard DP problems

Remember: Every string algorithm you learn makes you a better programmer! 💪

🌟 If this helped you, give it a ⭐ on GitHub! 🌟

Made with ❤️ for the coding community by Gaurav Goswami

⬅️ Previous: Arrays | 🏠 Home | Next: Linked Lists ➡️

Last Updated: December 2025
Licensed under MIT
Happy Coding! 💻✨