DSA Part 4: Strings

Strings are one of the most common data types in programming and appear in nearly every FAANG interview. A string is a sequence of characters—understanding their internal representation and common operations is essential.

String memory layout showing character array with indices and null terminator — String internal representation — a sequence of characters stored contiguously in memory with index-based access

                            
                            Key Insight: In Python, strings are immutable—every modification creates a new string. This has important implications for time complexity: string concatenation in a loop is \(O(n^{2})\), not \(O(n)\)!
                        

String Representation

Understanding how strings are stored in memory helps optimize string-heavy algorithms.

# String Representation and Character Encoding
# ASCII: 7-bit (128 chars), Extended ASCII: 8-bit (256 chars)
# Unicode: Up to 1,114,112 code points

# Character to ASCII
char = 'A'
print(f"'{char}' ? ASCII: {ord(char)}")  # 65

# ASCII to Character
ascii_val = 97
print(f"{ascii_val} ? Character: {chr(ascii_val)}")  # 'a'

# String to list of ASCII values
text = "Hello"
ascii_list = [ord(c) for c in text]
print(f"'{text}' ? ASCII: {ascii_list}")  # [72, 101, 108, 108, 111]

# Memory demonstration
import sys

s1 = "Hello"
s2 = "Hello World"
s3 = "Hello" * 100

print(f"\nString Memory Usage:")
print(f"'{s1}' (5 chars): {sys.getsizeof(s1)} bytes")
print(f"'{s2}' (11 chars): {sys.getsizeof(s2)} bytes")
print(f"'Hello' * 100 (500 chars): {sys.getsizeof(s3)} bytes")

# String interning (Python optimizes small strings)
a = "hello"
b = "hello"
print(f"\nString Interning:")
print(f"a = 'hello', b = 'hello'")
print(f"a is b: {a is b}")  # True - same object!

#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
    // Character to ASCII
    char c = 'A';
    cout << "'" << c << "' ? ASCII: " << (int)c << endl;  // 65
    
    // ASCII to Character
    int asciiVal = 97;
    cout << asciiVal << " ? Character: " << (char)asciiVal << endl;  // 'a'
    
    // String to vector of ASCII values
    string text = "Hello";
    vector<int> asciiList;
    cout << "'" << text << "' ? ASCII: [";
    for (int i = 0; i < text.length(); i++) {
        asciiList.push_back((int)text[i]);
        cout << (int)text[i];
        if (i < text.length() - 1) cout << ", ";
    }
    cout << "]" << endl;  // [72, 101, 108, 108, 111]
    
    // String memory - C++ strings are mutable!
    string s1 = "Hello";
    string s2 = "Hello World";
    
    cout << "\nString Sizes (C++ strings are mutable):" << endl;
    cout << "'" << s1 << "': capacity=" << s1.capacity() 
         << ", size=" << s1.size() << endl;
    cout << "'" << s2 << "': capacity=" << s2.capacity() 
         << ", size=" << s2.size() << endl;
    
    // No interning in C++ - each string is separate
    string a = "hello";
    string b = "hello";
    cout << "\nNo String Interning in C++:" << endl;
    cout << "a == b: " << (a == b ? "true" : "false") << endl;  // true (value)
    cout << "&a == &b: " << (&a == &b ? "true" : "false") << endl;  // false (different objects)
    
    return 0;
}

public class StringRepresentation {
    public static void main(String[] args) {
        // Character to ASCII
        char c = 'A';
        System.out.println("'" + c + "' ? ASCII: " + (int)c);  // 65
        
        // ASCII to Character
        int asciiVal = 97;
        System.out.println(asciiVal + " ? Character: " + (char)asciiVal);  // 'a'
        
        // String to array of ASCII values
        String text = "Hello";
        int[] asciiList = new int[text.length()];
        System.out.print("'" + text + "' ? ASCII: [");
        for (int i = 0; i < text.length(); i++) {
            asciiList[i] = (int)text.charAt(i);
            System.out.print(asciiList[i]);
            if (i < text.length() - 1) System.out.print(", ");
        }
        System.out.println("]");  // [72, 101, 108, 108, 111]
        
        // Java strings are immutable like Python
        String s1 = "Hello";
        String s2 = "Hello World";
        StringBuilder s3 = new StringBuilder();
        for (int i = 0; i < 100; i++) s3.append("Hello");
        
        System.out.println("\nString Memory (Java strings are immutable):");
        System.out.println("'" + s1 + "' (5 chars): " + s1.length() + " chars");
        System.out.println("'" + s2 + "' (11 chars): " + s2.length() + " chars");
        
        // String interning (Java pools literal strings)
        String a = "hello";
        String b = "hello";
        String c2 = new String("hello");
        
        System.out.println("\nString Interning in Java:");
        System.out.println("a == b: " + (a == b));  // true - same pooled object
        System.out.println("a == c (new String): " + (a == c2));  // false - different objects
        System.out.println("a.equals(c): " + a.equals(c2));  // true - same value
    }
}

Basic String Operations

Common string operations diagram showing concatenation, slicing, indexing, and searching — Basic string operations and their time complexities — indexing \(O(1)\), slicing \(O(k)\), concatenation O(n+m), and searching \(O(n)\)

# Common String Operations and Their Complexities

# 1. Length - O(1) in Python (stored as attribute)
s = "Hello World"
print(f"Length: {len(s)}")  # 11

# 2. Indexing - O(1)
print(f"First char: {s[0]}")   # 'H'
print(f"Last char: {s[-1]}")   # 'd'

# 3. Slicing - O(k) where k is slice length
print(f"Slice [0:5]: {s[0:5]}")     # 'Hello'
print(f"Slice [6:]: {s[6:]}")       # 'World'
print(f"Reverse: {s[::-1]}")        # 'dlroW olleH'

# 4. Concatenation - O(n+m) creates new string
s1 = "Hello"
s2 = "World"
s3 = s1 + " " + s2  # O(len(s1) + len(s2))
print(f"Concatenation: {s3}")

# 5. Membership testing - O(n)
print(f"'World' in s: {'World' in s}")  # True

# 6. Find/Index - O(n*m) worst case
text = "Hello World"
print(f"Find 'World': {text.find('World')}")    # 6
print(f"Find 'xyz': {text.find('xyz')}")        # -1

# 7. Count - O(n)
print(f"Count 'l': {text.count('l')}")  # 3

# 8. Split - O(n)
words = text.split()
print(f"Split: {words}")  # ['Hello', 'World']

# 9. Join - O(total_length)
joined = "-".join(words)
print(f"Join: {joined}")  # 'Hello-World'

# 10. Replace - O(n)
replaced = text.replace("World", "Python")
print(f"Replace: {replaced}")  # 'Hello Python'

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
using namespace std;

int main() {
    // 1. Length - O(1)
    string s = "Hello World";
    cout << "Length: " << s.length() << endl;  // 11
    
    // 2. Indexing - O(1)
    cout << "First char: " << s[0] << endl;      // 'H'
    cout << "Last char: " << s[s.length()-1] << endl;  // 'd'
    
    // 3. Substring - O(k)
    cout << "Substr [0,5): " << s.substr(0, 5) << endl;  // 'Hello'
    cout << "Substr [6,]: " << s.substr(6) << endl;      // 'World'
    
    // Reverse string
    string reversed = s;
    reverse(reversed.begin(), reversed.end());
    cout << "Reverse: " << reversed << endl;  // 'dlroW olleH'
    
    // 4. Concatenation - O(n+m), but C++ strings are mutable
    string s1 = "Hello";
    string s2 = "World";
    string s3 = s1 + " " + s2;
    cout << "Concatenation: " << s3 << endl;
    
    // 5. Find substring - O(n*m) worst
    string text = "Hello World";
    size_t pos = text.find("World");
    cout << "Find 'World': " << pos << endl;  // 6
    pos = text.find("xyz");
    cout << "Find 'xyz': " << (pos == string::npos ? -1 : (int)pos) << endl;  // -1
    
    // 6. Count occurrences - O(n)
    int count = 0;
    for (char c : text) if (c == 'l') count++;
    cout << "Count 'l': " << count << endl;  // 3
    
    // 7. Split - O(n) using stringstream
    vector<string> words;
    istringstream iss(text);
    string word;
    while (iss >> word) words.push_back(word);
    cout << "Split: [";
    for (int i = 0; i < words.size(); i++) {
        cout << "'" << words[i] << "'";
        if (i < words.size()-1) cout << ", ";
    }
    cout << "]" << endl;  // ['Hello', 'World']
    
    // 8. Join - O(total_length)
    string joined;
    for (int i = 0; i < words.size(); i++) {
        joined += words[i];
        if (i < words.size()-1) joined += "-";
    }
    cout << "Join: " << joined << endl;  // 'Hello-World'
    
    // 9. Replace - using algorithm
    string replaced = text;
    size_t start = replaced.find("World");
    if (start != string::npos) {
        replaced.replace(start, 5, "C++");
    }
    cout << "Replace: " << replaced << endl;  // 'Hello C++'
    
    return 0;
}

import java.util.*;

public class StringOperations {
    public static void main(String[] args) {
        // 1. Length - O(1)
        String s = "Hello World";
        System.out.println("Length: " + s.length());  // 11
        
        // 2. Indexing - O(1)
        System.out.println("First char: " + s.charAt(0));  // 'H'
        System.out.println("Last char: " + s.charAt(s.length()-1));  // 'd'
        
        // 3. Substring - O(k)
        System.out.println("Substring [0,5): " + s.substring(0, 5));  // 'Hello'
        System.out.println("Substring [6,]: " + s.substring(6));      // 'World'
        
        // Reverse string
        String reversed = new StringBuilder(s).reverse().toString();
        System.out.println("Reverse: " + reversed);  // 'dlroW olleH'
        
        // 4. Concatenation - O(n+m), use StringBuilder for efficiency
        String s1 = "Hello";
        String s2 = "World";
        String s3 = s1 + " " + s2;
        System.out.println("Concatenation: " + s3);
        
        // 5. Find substring - O(n*m) worst
        String text = "Hello World";
        System.out.println("Find 'World': " + text.indexOf("World"));  // 6
        System.out.println("Find 'xyz': " + text.indexOf("xyz"));      // -1
        
        // 6. Count occurrences - O(n)
        int count = 0;
        for (char c : text.toCharArray()) {
            if (c == 'l') count++;
        }
        System.out.println("Count 'l': " + count);  // 3
        
        // 7. Split - O(n)
        String[] words = text.split(" ");
        System.out.println("Split: " + Arrays.toString(words));  // [Hello, World]
        
        // 8. Join - O(total_length)
        String joined = String.join("-", words);
        System.out.println("Join: " + joined);  // 'Hello-World'
        
        // 9. Replace - O(n)
        String replaced = text.replace("World", "Java");
        System.out.println("Replace: " + replaced);  // 'Hello Java'
    }
}

Efficient String Building

# String Building: Wrong vs Right Way

import time

# WRONG: String concatenation in loop - O(n²)
def build_string_wrong(n):
    result = ""
    for i in range(n):
        result += str(i)  # Creates new string each time!
    return result

# RIGHT: Using list and join - O(n)
def build_string_right(n):
    parts = []
    for i in range(n):
        parts.append(str(i))
    return "".join(parts)

# ALSO RIGHT: List comprehension + join - O(n)
def build_string_comprehension(n):
    return "".join(str(i) for i in range(n))

# Performance comparison
n = 10000

start = time.time()
build_string_wrong(n)
wrong_time = time.time() - start

start = time.time()
build_string_right(n)
right_time = time.time() - start

start = time.time()
build_string_comprehension(n)
comp_time = time.time() - start

print(f"String Building Performance (n={n}):")
print(f"  Concatenation (wrong): {wrong_time:.4f}s")
print(f"  List + join (right):   {right_time:.4f}s")
print(f"  Comprehension + join:  {comp_time:.4f}s")
print(f"  Speedup: {wrong_time/right_time:.1f}x faster!")

#include <iostream>
#include <string>
#include <sstream>
#include <chrono>
using namespace std;
using namespace std::chrono;

// SLOWER: String concatenation (still O(n) due to mutable strings, but less efficient)
string buildStringConcat(int n) {
    string result = "";
    for (int i = 0; i < n; i++) {
        result += to_string(i);  // Repeated reallocations
    }
    return result;
}

// BETTER: Reserve capacity first
string buildStringReserve(int n) {
    string result;
    result.reserve(n * 4);  // Pre-allocate space
    for (int i = 0; i < n; i++) {
        result += to_string(i);
    }
    return result;
}

// BEST: Use stringstream
string buildStringStream(int n) {
    stringstream ss;
    for (int i = 0; i < n; i++) {
        ss << i;
    }
    return ss.str();
}

int main() {
    int n = 100000;
    
    auto start = high_resolution_clock::now();
    buildStringConcat(n);
    auto concatTime = duration_cast<milliseconds>(
        high_resolution_clock::now() - start).count();
    
    start = high_resolution_clock::now();
    buildStringReserve(n);
    auto reserveTime = duration_cast<milliseconds>(
        high_resolution_clock::now() - start).count();
    
    start = high_resolution_clock::now();
    buildStringStream(n);
    auto streamTime = duration_cast<milliseconds>(
        high_resolution_clock::now() - start).count();
    
    cout << "String Building Performance (n=" << n << "):" << endl;
    cout << "  Concatenation:  " << concatTime << "ms" << endl;
    cout << "  With reserve(): " << reserveTime << "ms" << endl;
    cout << "  StringStream:   " << streamTime << "ms" << endl;
    
    return 0;
}

public class StringBuilding {
    // WRONG: String concatenation in loop - O(n²) due to immutable strings
    static String buildStringWrong(int n) {
        String result = "";
        for (int i = 0; i < n; i++) {
            result += i;  // Creates new String each time!
        }
        return result;
    }
    
    // RIGHT: Using StringBuilder - O(n)
    static String buildStringRight(int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(i);
        }
        return sb.toString();
    }
    
    // ALSO RIGHT: With initial capacity for better performance
    static String buildStringCapacity(int n) {
        StringBuilder sb = new StringBuilder(n * 4);  // Pre-allocate
        for (int i = 0; i < n; i++) {
            sb.append(i);
        }
        return sb.toString();
    }
    
    public static void main(String[] args) {
        int n = 10000;
        
        long start = System.nanoTime();
        buildStringWrong(n);
        long wrongTime = (System.nanoTime() - start) / 1_000_000;
        
        start = System.nanoTime();
        buildStringRight(n);
        long rightTime = (System.nanoTime() - start) / 1_000_000;
        
        start = System.nanoTime();
        buildStringCapacity(n);
        long capTime = (System.nanoTime() - start) / 1_000_000;
        
        System.out.println("String Building Performance (n=" + n + "):");
        System.out.println("  Concatenation (wrong):   " + wrongTime + "ms");
        System.out.println("  StringBuilder (right):   " + rightTime + "ms");
        System.out.println("  With capacity:           " + capTime + "ms");
        if (rightTime > 0) {
            System.out.println("  Speedup: " + (wrongTime/rightTime) + "x faster!");
        }
    }
}

Pattern Matching Algorithms

Pattern matching—finding a pattern within a text—is a fundamental problem with applications in text editors, search engines, and bioinformatics.

Pattern matching algorithm comparison showing naive sliding window versus KMP prefix table approach — Pattern matching algorithms — the naive approach slides the pattern one position at a time, while KMP uses a prefix table to skip redundant comparisons

Naive (Brute Force) Algorithm

The brute force approach slides the pattern across the text one character at a time, checking for a full match at each position. At position \(i\), compare text[i..i+m-1] with pattern[0..m-1]. If any character mismatches, shift right by 1 and restart. Worst case \(O(nm)\) occurs with pathological inputs like searching "AAAB" in "AAAAAAA..." (many partial matches that fail at the last character). Despite poor worst-case, this is acceptable for short patterns and random text.

# Naive Pattern Matching
# Time: O((n-m+1) × m) where n=text length, m=pattern length
# Space: O(1)

def naive_search(text, pattern):
    """
    Find all occurrences of pattern in text.
    Returns list of starting indices.
    """
    n = len(text)
    m = len(pattern)
    occurrences = []
    
    # Slide pattern over text
    for i in range(n - m + 1):
        match = True
        # Check each character
        for j in range(m):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            occurrences.append(i)
    
    return occurrences

# Test
text = "AABAACAADAABAAABAA"
pattern = "AABA"

result = naive_search(text, pattern)
print(f"Text: {text}")
print(f"Pattern: {pattern}")
print(f"Found at indices: {result}")  # [0, 9, 13]

# Visualize matches
for idx in result:
    print(f"  Position {idx}: {text[idx:idx+len(pattern)]}")

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Naive Pattern Matching
// Time: O((n-m+1) × m), Space: O(1)
vector<int> naiveSearch(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> occurrences;
    
    // Slide pattern over text
    for (int i = 0; i <= n - m; i++) {
        bool match = true;
        // Check each character
        for (int j = 0; j < m; j++) {
            if (text[i + j] != pattern[j]) {
                match = false;
                break;
            }
        }
        if (match) {
            occurrences.push_back(i);
        }
    }
    
    return occurrences;
}

int main() {
    string text = "AABAACAADAABAAABAA";
    string pattern = "AABA";
    
    vector<int> result = naiveSearch(text, pattern);
    
    cout << "Text: " << text << endl;
    cout << "Pattern: " << pattern << endl;
    cout << "Found at indices: [";
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) cout << ", ";
    }
    cout << "]" << endl;  // [0, 9, 13]
    
    // Visualize matches
    for (int idx : result) {
        cout << "  Position " << idx << ": " 
             << text.substr(idx, pattern.length()) << endl;
    }
    
    return 0;
}

import java.util.*;

public class NaivePatternMatch {
    // Naive Pattern Matching
    // Time: O((n-m+1) × m), Space: O(1)
    static List<Integer> naiveSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        List<Integer> occurrences = new ArrayList<>();
        
        // Slide pattern over text
        for (int i = 0; i <= n - m; i++) {
            boolean match = true;
            // Check each character
            for (int j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    match = false;
                    break;
                }
            }
            if (match) {
                occurrences.add(i);
            }
        }
        
        return occurrences;
    }
    
    public static void main(String[] args) {
        String text = "AABAACAADAABAAABAA";
        String pattern = "AABA";
        
        List<Integer> result = naiveSearch(text, pattern);
        
        System.out.println("Text: " + text);
        System.out.println("Pattern: " + pattern);
        System.out.println("Found at indices: " + result);  // [0, 9, 13]
        
        // Visualize matches
        for (int idx : result) {
            System.out.println("  Position " + idx + ": " + 
                             text.substring(idx, idx + pattern.length()));
        }
    }
}

KMP (Knuth-Morris-Pratt) Algorithm

KMP achieves \(O(n + m)\) by never re-examining text characters. The key insight: when a mismatch occurs after matching \(k\) characters, the LPS (Longest Proper Prefix which is also Suffix) table tells you how far you can skip without missing any potential match. If the first \(k\) characters matched, and the LPS value for position \(k-1\) is \(j\), then the first \(j\) characters of the pattern already align correctly — resume matching from position \(j\) instead of restarting from 0.

Analogy: Imagine searching for "ABCABD" in text. If you've matched "ABCAB" and the next character fails, KMP knows that the suffix "AB" of what you matched is also a prefix of the pattern — so you can "slide" to reuse those 2 characters instead of starting over.

                            
                            LPS Array: Longest Proper Prefix which is also Suffix. For pattern "AABAAC", LPS = [0, 1, 0, 1, 2, 0].
                        

# KMP Pattern Matching Algorithm
# Time: O(n + m) - linear!
# Space: O(m) for LPS array

def compute_lps(pattern):
    """
    Compute Longest Proper Prefix which is also Suffix (LPS) array.
    
    LPS[i] = length of longest proper prefix of pattern[0..i]
             which is also a suffix of pattern[0..i]
    """
    m = len(pattern)
    lps = [0] * m
    
    length = 0  # Length of previous longest prefix suffix
    i = 1
    
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                # Try shorter prefix
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    
    return lps

def kmp_search(text, pattern):
    """
    KMP pattern matching algorithm.
    Returns list of starting indices where pattern is found.
    """
    n = len(text)
    m = len(pattern)
    
    if m == 0:
        return []
    
    # Compute LPS array
    lps = compute_lps(pattern)
    
    occurrences = []
    i = 0  # Index for text
    j = 0  # Index for pattern
    
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        
        if j == m:
            # Found pattern
            occurrences.append(i - j)
            j = lps[j - 1]  # Use LPS to skip
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]  # Use LPS to skip
            else:
                i += 1
    
    return occurrences

# Test KMP
text = "AABAACAADAABAAABAA"
pattern = "AABA"

lps = compute_lps(pattern)
print(f"Pattern: {pattern}")
print(f"LPS array: {lps}")

result = kmp_search(text, pattern)
print(f"\nText: {text}")
print(f"Pattern found at: {result}")  # [0, 9, 13]

# Step-by-step LPS example
pattern2 = "AABAACAAB"
lps2 = compute_lps(pattern2)
print(f"\nPattern: {pattern2}")
print(f"Index:   {list(range(len(pattern2)))}")
print(f"LPS:     {lps2}")

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Compute LPS (Longest Proper Prefix which is also Suffix) array
vector<int> computeLPS(const string& pattern) {
    int m = pattern.length();
    vector<int> lps(m, 0);
    
    int length = 0;  // Length of previous longest prefix suffix
    int i = 1;
    
    while (i < m) {
        if (pattern[i] == pattern[length]) {
            length++;
            lps[i] = length;
            i++;
        } else {
            if (length != 0) {
                // Try shorter prefix
                length = lps[length - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    
    return lps;
}

// KMP Pattern Matching - O(n + m)
vector<int> kmpSearch(const string& text, const string& pattern) {
    int n = text.length();
    int m = pattern.length();
    vector<int> occurrences;
    
    if (m == 0) return occurrences;
    
    vector<int> lps = computeLPS(pattern);
    
    int i = 0;  // Index for text
    int j = 0;  // Index for pattern
    
    while (i < n) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        
        if (j == m) {
            // Found pattern
            occurrences.push_back(i - j);
            j = lps[j - 1];  // Use LPS to skip
        } else if (i < n && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];  // Use LPS to skip
            } else {
                i++;
            }
        }
    }
    
    return occurrences;
}

int main() {
    string text = "AABAACAADAABAAABAA";
    string pattern = "AABA";
    
    vector<int> lps = computeLPS(pattern);
    cout << "Pattern: " << pattern << endl;
    cout << "LPS array: [";
    for (int i = 0; i < lps.size(); i++) {
        cout << lps[i];
        if (i < lps.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
    
    vector<int> result = kmpSearch(text, pattern);
    cout << "\nText: " << text << endl;
    cout << "Pattern found at: [";
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) cout << ", ";
    }
    cout << "]" << endl;  // [0, 9, 13]
    
    return 0;
}

import java.util.*;

public class KMPAlgorithm {
    // Compute LPS (Longest Proper Prefix which is also Suffix) array
    static int[] computeLPS(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        
        int length = 0;  // Length of previous longest prefix suffix
        int i = 1;
        
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    // Try shorter prefix
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        return lps;
    }
    
    // KMP Pattern Matching - O(n + m)
    static List<Integer> kmpSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        List<Integer> occurrences = new ArrayList<>();
        
        if (m == 0) return occurrences;
        
        int[] lps = computeLPS(pattern);
        
        int i = 0;  // Index for text
        int j = 0;  // Index for pattern
        
        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            
            if (j == m) {
                // Found pattern
                occurrences.add(i - j);
                j = lps[j - 1];  // Use LPS to skip
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];  // Use LPS to skip
                } else {
                    i++;
                }
            }
        }
        
        return occurrences;
    }
    
    public static void main(String[] args) {
        String text = "AABAACAADAABAAABAA";
        String pattern = "AABA";
        
        int[] lps = computeLPS(pattern);
        System.out.println("Pattern: " + pattern);
        System.out.println("LPS array: " + Arrays.toString(lps));
        
        List<Integer> result = kmpSearch(text, pattern);
        System.out.println("\nText: " + text);
        System.out.println("Pattern found at: " + result);  // [0, 9, 13]
    }
}

Rabin-Karp Algorithm

Rabin-Karp uses rolling hashes for pattern matching: compute a hash of the pattern, then slide a window across the text computing the hash of each window. If hashes match, verify character-by-character (to handle hash collisions). The "rolling" part: when the window shifts right by 1, the new hash is computed from the old hash in \(O(1)\) by removing the leftmost character's contribution and adding the new rightmost character's. Average case: \(O(n + m)\). Rabin-Karp excels at multi-pattern search (search for many patterns simultaneously) and is the basis for plagiarism detection tools.

# Rabin-Karp Algorithm with Rolling Hash
# Average Time: O(n + m)
# Worst Time: O(n × m) - many hash collisions
# Space: O(1)

def rabin_karp(text, pattern, base=256, prime=101):
    """
    Rabin-Karp pattern matching using rolling hash.
    
    Hash function: h = (c[0]*base^(m-1) + c[1]*base^(m-2) + ... + c[m-1]) % prime
    
    Rolling hash: Remove first char, add new char
    new_hash = (base * (old_hash - text[i-1] * base^(m-1)) + text[i+m-1]) % prime
    """
    n = len(text)
    m = len(pattern)
    occurrences = []
    
    if m > n:
        return occurrences
    
    # Precompute base^(m-1) % prime
    h = pow(base, m - 1, prime)
    
    # Calculate hash of pattern and first window of text
    pattern_hash = 0
    text_hash = 0
    
    for i in range(m):
        pattern_hash = (base * pattern_hash + ord(pattern[i])) % prime
        text_hash = (base * text_hash + ord(text[i])) % prime
    
    # Slide pattern over text
    for i in range(n - m + 1):
        # Check hash match
        if pattern_hash == text_hash:
            # Verify character by character (avoid false positives)
            if text[i:i+m] == pattern:
                occurrences.append(i)
        
        # Calculate hash for next window using rolling hash
        if i < n - m:
            # Remove leading digit, add trailing digit
            text_hash = (base * (text_hash - ord(text[i]) * h) + ord(text[i + m])) % prime
            
            # Handle negative hash
            if text_hash < 0:
                text_hash += prime
    
    return occurrences

# Test Rabin-Karp
text = "AABAACAADAABAAABAA"
pattern = "AABA"

result = rabin_karp(text, pattern)
print(f"Text: {text}")
print(f"Pattern: {pattern}")
print(f"Found at indices: {result}")  # [0, 9, 13]

# Hash collision demonstration
print("\nHash values during search:")
m = len(pattern)
for i in range(len(text) - m + 1):
    window = text[i:i+m]
    h = sum(ord(c) * (256 ** (m-1-j)) for j, c in enumerate(window)) % 101
    match = "? MATCH!" if window == pattern else ""
    print(f"  Window '{window}': hash={h} {match}")

#include <iostream>
#include <string>
#include <vector>
using namespace std;

// Rabin-Karp Algorithm with Rolling Hash
// Average Time: O(n + m), Worst: O(n × m)
vector<int> rabinKarp(const string& text, const string& pattern, 
                       int base = 256, int prime = 101) {
    int n = text.length();
    int m = pattern.length();
    vector<int> occurrences;
    
    if (m > n) return occurrences;
    
    // Precompute base^(m-1) % prime
    long long h = 1;
    for (int i = 0; i < m - 1; i++) {
        h = (h * base) % prime;
    }
    
    // Calculate hash of pattern and first window of text
    long long patternHash = 0;
    long long textHash = 0;
    
    for (int i = 0; i < m; i++) {
        patternHash = (base * patternHash + pattern[i]) % prime;
        textHash = (base * textHash + text[i]) % prime;
    }
    
    // Slide pattern over text
    for (int i = 0; i <= n - m; i++) {
        // Check hash match
        if (patternHash == textHash) {
            // Verify character by character
            bool match = true;
            for (int j = 0; j < m; j++) {
                if (text[i + j] != pattern[j]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                occurrences.push_back(i);
            }
        }
        
        // Calculate hash for next window (rolling hash)
        if (i < n - m) {
            textHash = (base * (textHash - text[i] * h) + text[i + m]) % prime;
            
            // Handle negative hash
            if (textHash < 0) {
                textHash += prime;
            }
        }
    }
    
    return occurrences;
}

int main() {
    string text = "AABAACAADAABAAABAA";
    string pattern = "AABA";
    
    vector<int> result = rabinKarp(text, pattern);
    
    cout << "Text: " << text << endl;
    cout << "Pattern: " << pattern << endl;
    cout << "Found at indices: [";
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) cout << ", ";
    }
    cout << "]" << endl;  // [0, 9, 13]
    
    return 0;
}

import java.util.*;

public class RabinKarpAlgorithm {
    // Rabin-Karp Algorithm with Rolling Hash
    // Average Time: O(n + m), Worst: O(n × m)
    static List<Integer> rabinKarp(String text, String pattern, 
                                     int base, int prime) {
        int n = text.length();
        int m = pattern.length();
        List<Integer> occurrences = new ArrayList<>();
        
        if (m > n) return occurrences;
        
        // Precompute base^(m-1) % prime
        long h = 1;
        for (int i = 0; i < m - 1; i++) {
            h = (h * base) % prime;
        }
        
        // Calculate hash of pattern and first window of text
        long patternHash = 0;
        long textHash = 0;
        
        for (int i = 0; i < m; i++) {
            patternHash = (base * patternHash + pattern.charAt(i)) % prime;
            textHash = (base * textHash + text.charAt(i)) % prime;
        }
        
        // Slide pattern over text
        for (int i = 0; i <= n - m; i++) {
            // Check hash match
            if (patternHash == textHash) {
                // Verify character by character
                if (text.substring(i, i + m).equals(pattern)) {
                    occurrences.add(i);
                }
            }
            
            // Calculate hash for next window (rolling hash)
            if (i < n - m) {
                textHash = (base * (textHash - text.charAt(i) * h) 
                           + text.charAt(i + m)) % prime;
                
                // Handle negative hash
                if (textHash < 0) {
                    textHash += prime;
                }
            }
        }
        
        return occurrences;
    }
    
    public static void main(String[] args) {
        String text = "AABAACAADAABAAABAA";
        String pattern = "AABA";
        
        List<Integer> result = rabinKarp(text, pattern, 256, 101);
        
        System.out.println("Text: " + text);
        System.out.println("Pattern: " + pattern);
        System.out.println("Found at indices: " + result);  // [0, 9, 13]
    }
}

Pattern Matching Comparison

Algorithm	Preprocessing	Search Time	Best For
Naive	None	O(n×m)	Short patterns, simple cases
KMP	O(m)	\(O(n)\)	Single pattern, guaranteed linear
Rabin-Karp	O(m)	\(O(n)\) average	Multiple patterns, plagiarism detection

Palindrome Algorithms

Palindromes read the same forwards and backwards. They appear frequently in interviews!

Palindrome two-pointer technique showing left and right pointers moving inward to check character equality — Palindrome checking with the two-pointer technique — left and right pointers converge toward the center, comparing characters at each step

# Palindrome Checking Methods

def is_palindrome_two_pointer(s):
    """
    Two-pointer approach.
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    
    return True

def is_palindrome_reverse(s):
    """
    Reverse and compare.
    Time: O(n), Space: O(n)
    """
    return s == s[::-1]

def is_palindrome_recursive(s):
    """
    Recursive approach.
    Time: O(n), Space: O(n) - call stack
    """
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome_recursive(s[1:-1])

def is_valid_palindrome(s):
    """
    Check palindrome ignoring non-alphanumeric and case.
    LeetCode 125 - Valid Palindrome
    Time: O(n), Space: O(1)
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        # Skip non-alphanumeric from left
        while left < right and not s[left].isalnum():
            left += 1
        # Skip non-alphanumeric from right
        while left < right and not s[right].isalnum():
            right -= 1
        
        if s[left].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True

# Test palindrome functions
test_strings = ["racecar", "hello", "A man a plan a canal Panama", "12321"]

print("Palindrome Tests:")
for s in test_strings:
    clean = ''.join(c.lower() for c in s if c.isalnum())
    result = is_palindrome_two_pointer(clean)
    print(f"  '{s}' ? {result}")

# Valid palindrome (with special chars)
print("\nValid Palindrome (ignoring case/special chars):")
print(f"  'A man, a plan, a canal: Panama' ? {is_valid_palindrome('A man, a plan, a canal: Panama')}")
print(f"  'race a car' ? {is_valid_palindrome('race a car')}")

#include <iostream>
#include <string>
#include <algorithm>
#include <cctype>
using namespace std;

// Two-pointer approach - O(n), O(1)
bool isPalindromeTwoPointer(const string& s) {
    int left = 0, right = s.length() - 1;
    
    while (left < right) {
        if (s[left] != s[right]) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

// Reverse and compare - O(n), O(n)
bool isPalindromeReverse(const string& s) {
    string reversed = s;
    reverse(reversed.begin(), reversed.end());
    return s == reversed;
}

// Recursive approach - O(n), O(n) stack
bool isPalindromeRecursive(const string& s, int left, int right) {
    if (left >= right) return true;
    if (s[left] != s[right]) return false;
    return isPalindromeRecursive(s, left + 1, right - 1);
}

// Valid palindrome ignoring non-alphanumeric - LeetCode 125
bool isValidPalindrome(const string& s) {
    int left = 0, right = s.length() - 1;
    
    while (left < right) {
        // Skip non-alphanumeric from left
        while (left < right && !isalnum(s[left])) left++;
        // Skip non-alphanumeric from right
        while (left < right && !isalnum(s[right])) right--;
        
        if (tolower(s[left]) != tolower(s[right])) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

int main() {
    // Test cases
    string tests[] = {"racecar", "hello", "12321"};
    
    cout << "Palindrome Tests:" << endl;
    for (const string& s : tests) {
        cout << "  '" << s << "' ? " 
             << (isPalindromeTwoPointer(s) ? "true" : "false") << endl;
    }
    
    cout << "\nValid Palindrome (ignoring case/special chars):" << endl;
    cout << "  'A man, a plan, a canal: Panama' ? " 
         << (isValidPalindrome("A man, a plan, a canal: Panama") ? "true" : "false") 
         << endl;
    cout << "  'race a car' ? " 
         << (isValidPalindrome("race a car") ? "true" : "false") << endl;
    
    return 0;
}

public class PalindromeCheck {
    // Two-pointer approach - O(n), O(1)
    static boolean isPalindromeTwoPointer(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;
    }
    
    // Reverse and compare - O(n), O(n)
    static boolean isPalindromeReverse(String s) {
        String reversed = new StringBuilder(s).reverse().toString();
        return s.equals(reversed);
    }
    
    // Recursive approach - O(n), O(n) stack
    static boolean isPalindromeRecursive(String s, int left, int right) {
        if (left >= right) return true;
        if (s.charAt(left) != s.charAt(right)) return false;
        return isPalindromeRecursive(s, left + 1, right - 1);
    }
    
    // Valid palindrome ignoring non-alphanumeric - LeetCode 125
    static boolean isValidPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        
        while (left < right) {
            // Skip non-alphanumeric from left
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            // Skip non-alphanumeric from right
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            
            if (Character.toLowerCase(s.charAt(left)) != 
                Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        
        return true;
    }
    
    public static void main(String[] args) {
        String[] tests = {"racecar", "hello", "12321"};
        
        System.out.println("Palindrome Tests:");
        for (String s : tests) {
            System.out.println("  '" + s + "' ? " + isPalindromeTwoPointer(s));
        }
        
        System.out.println("\nValid Palindrome (ignoring case/special chars):");
        System.out.println("  'A man, a plan, a canal: Panama' ? " + 
            isValidPalindrome("A man, a plan, a canal: Panama"));
        System.out.println("  'race a car' ? " + 
            isValidPalindrome("race a car"));
    }
}

Longest Palindromic Substring

Finding the longest palindromic substring is a classic interview question. The expand-around-center approach is optimal for interviews.

# Longest Palindromic Substring
# Expand Around Center Approach
# Time: O(n²), Space: O(1)

def longest_palindrome(s):
    """
    Find longest palindromic substring using expand around center.
    
    Key insight: A palindrome mirrors around its center.
    There are 2n-1 such centers (n single chars + n-1 between chars).
    """
    if not s:
        return ""
    
    def expand_around_center(left, right):
        """Expand outward while characters match."""
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        # Return the palindrome (left+1 to right-1 inclusive)
        return s[left + 1:right]
    
    result = ""
    
    for i in range(len(s)):
        # Odd length palindrome (single center)
        odd = expand_around_center(i, i)
        if len(odd) > len(result):
            result = odd
        
        # Even length palindrome (two centers)
        even = expand_around_center(i, i + 1)
        if len(even) > len(result):
            result = even
    
    return result

# Test
test_strings = ["babad", "cbbd", "abcba", "ac", "a", "racecar"]

print("Longest Palindromic Substring:")
for s in test_strings:
    result = longest_palindrome(s)
    print(f"  '{s}' ? '{result}' (length {len(result)})")

# Trace example
s = "babad"
print(f"\nTrace for '{s}':")
for i in range(len(s)):
    print(f"  Center at index {i} ('{s[i]}'):")
    
    # Odd expansion
    l, r = i, i
    while l >= 0 and r < len(s) and s[l] == s[r]:
        print(f"    Odd: '{s[l:r+1]}'")
        l -= 1
        r += 1
    
    # Even expansion
    l, r = i, i + 1
    while l >= 0 and r < len(s) and s[l] == s[r]:
        print(f"    Even: '{s[l:r+1]}'")
        l -= 1
        r += 1

#include <iostream>
#include <string>
using namespace std;

// Longest Palindromic Substring - Expand Around Center
// Time: O(n²), Space: O(1)
string longestPalindrome(const string& s) {
    if (s.empty()) return "";
    
    int start = 0, maxLen = 1;
    
    // Helper to expand around center
    auto expandAroundCenter = [&](int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            if (right - left + 1 > maxLen) {
                start = left;
                maxLen = right - left + 1;
            }
            left--;
            right++;
        }
    };
    
    for (int i = 0; i < s.length(); i++) {
        // Odd length palindrome
        expandAroundCenter(i, i);
        
        // Even length palindrome
        expandAroundCenter(i, i + 1);
    }
    
    return s.substr(start, maxLen);
}

int main() {
    string tests[] = {"babad", "cbbd", "abcba", "ac", "a", "racecar"};
    
    cout << "Longest Palindromic Substring:" << endl;
    for (const string& s : tests) {
        string result = longestPalindrome(s);
        cout << "  '" << s << "' ? '" << result 
             << "' (length " << result.length() << ")" << endl;
    }
    
    return 0;
}

public class LongestPalindrome {
    // Longest Palindromic Substring - Expand Around Center
    // Time: O(n²), Space: O(1)
    
    static int start = 0, maxLen = 1;
    
    static void expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && 
               s.charAt(left) == s.charAt(right)) {
            if (right - left + 1 > maxLen) {
                start = left;
                maxLen = right - left + 1;
            }
            left--;
            right++;
        }
    }
    
    static String longestPalindrome(String s) {
        if (s == null || s.isEmpty()) return "";
        
        start = 0;
        maxLen = 1;
        
        for (int i = 0; i < s.length(); i++) {
            // Odd length palindrome
            expandAroundCenter(s, i, i);
            
            // Even length palindrome
            expandAroundCenter(s, i, i + 1);
        }
        
        return s.substring(start, start + maxLen);
    }
    
    public static void main(String[] args) {
        String[] tests = {"babad", "cbbd", "abcba", "ac", "a", "racecar"};
        
        System.out.println("Longest Palindromic Substring:");
        for (String s : tests) {
            String result = longestPalindrome(s);
            System.out.println("  '" + s + "' ? '" + result + 
                             "' (length " + result.length() + ")");
        }
    }
}

Anagram Algorithms

Anagrams are words formed by rearranging letters of another word. They're common in interview questions!

Anagram detection using character frequency counting with hash map comparison — Anagram detection via character frequency counting — two strings are anagrams if and only if their character frequency maps are identical

# Anagram Detection Methods
from collections import Counter

def is_anagram_sort(s1, s2):
    """
    Check anagram by sorting.
    Time: O(n log n), Space: O(n)
    """
    return sorted(s1) == sorted(s2)

def is_anagram_count(s1, s2):
    """
    Check anagram using character count.
    Time: O(n), Space: O(1) - fixed alphabet
    """
    if len(s1) != len(s2):
        return False
    
    # Count characters
    count = [0] * 26  # Assuming lowercase a-z
    
    for c1, c2 in zip(s1, s2):
        count[ord(c1) - ord('a')] += 1
        count[ord(c2) - ord('a')] -= 1
    
    return all(c == 0 for c in count)

def is_anagram_counter(s1, s2):
    """
    Check anagram using Counter.
    Time: O(n), Space: O(n)
    """
    return Counter(s1) == Counter(s2)

# Test anagram detection
pairs = [
    ("listen", "silent"),
    ("hello", "world"),
    ("anagram", "nagaram"),
    ("rat", "car")
]

print("Anagram Detection:")
for s1, s2 in pairs:
    result = is_anagram_count(s1, s2)
    print(f"  '{s1}' vs '{s2}': {result}")

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

// Check anagram by sorting - O(n log n), O(n)
bool isAnagramSort(string s1, string s2) {
    sort(s1.begin(), s1.end());
    sort(s2.begin(), s2.end());
    return s1 == s2;
}

// Check anagram using character count - O(n), O(1)
bool isAnagramCount(const string& s1, const string& s2) {
    if (s1.length() != s2.length()) return false;
    
    int count[26] = {0};  // Assuming lowercase a-z
    
    for (int i = 0; i < s1.length(); i++) {
        count[s1[i] - 'a']++;
        count[s2[i] - 'a']--;
    }
    
    for (int i = 0; i < 26; i++) {
        if (count[i] != 0) return false;
    }
    
    return true;
}

int main() {
    vector<pair<string, string>> pairs = {
        {"listen", "silent"},
        {"hello", "world"},
        {"anagram", "nagaram"},
        {"rat", "car"}
    };
    
    cout << "Anagram Detection:" << endl;
    for (const auto& p : pairs) {
        bool result = isAnagramCount(p.first, p.second);
        cout << "  '" << p.first << "' vs '" << p.second 
             << "': " << (result ? "true" : "false") << endl;
    }
    
    return 0;
}

import java.util.*;

public class AnagramDetection {
    // Check anagram by sorting - O(n log n), O(n)
    static boolean isAnagramSort(String s1, String s2) {
        char[] arr1 = s1.toCharArray();
        char[] arr2 = s2.toCharArray();
        Arrays.sort(arr1);
        Arrays.sort(arr2);
        return Arrays.equals(arr1, arr2);
    }
    
    // Check anagram using character count - O(n), O(1)
    static boolean isAnagramCount(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        
        int[] count = new int[26];  // Assuming lowercase a-z
        
        for (int i = 0; i < s1.length(); i++) {
            count[s1.charAt(i) - 'a']++;
            count[s2.charAt(i) - 'a']--;
        }
        
        for (int c : count) {
            if (c != 0) return false;
        }
        
        return true;
    }
    
    public static void main(String[] args) {
        String[][] pairs = {
            {"listen", "silent"},
            {"hello", "world"},
            {"anagram", "nagaram"},
            {"rat", "car"}
        };
        
        System.out.println("Anagram Detection:");
        for (String[] p : pairs) {
            boolean result = isAnagramCount(p[0], p[1]);
            System.out.println("  '" + p[0] + "' vs '" + p[1] + "': " + result);
        }
    }
}

Group Anagrams

# Group Anagrams - LeetCode 49
# Time: O(n × k log k) where n=words, k=max word length
# Space: O(n × k)

from collections import defaultdict

def group_anagrams_sort(strs):
    """
    Group anagrams using sorted string as key.
    """
    groups = defaultdict(list)
    
    for s in strs:
        # Sorted string is the key
        key = tuple(sorted(s))
        groups[key].append(s)
    
    return list(groups.values())

def group_anagrams_count(strs):
    """
    Group anagrams using character count as key.
    Time: O(n × k) - no sorting needed
    """
    groups = defaultdict(list)
    
    for s in strs:
        # Character count tuple as key
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        key = tuple(count)
        groups[key].append(s)
    
    return list(groups.values())

# Test group anagrams
words = ["eat", "tea", "tan", "ate", "nat", "bat"]

print(f"Words: {words}")
print(f"\nGrouped (sort method):")
for group in group_anagrams_sort(words):
    print(f"  {group}")

print(f"\nGrouped (count method):")
for group in group_anagrams_count(words):
    print(f"  {group}")

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

// Group Anagrams - LeetCode 49
// Using sorted string as key - O(n × k log k)
vector<vector<string>> groupAnagramsSort(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    
    for (const string& s : strs) {
        string key = s;
        sort(key.begin(), key.end());
        groups[key].push_back(s);
    }
    
    vector<vector<string>> result;
    for (auto& p : groups) {
        result.push_back(move(p.second));
    }
    
    return result;
}

// Using character count as key - O(n × k)
vector<vector<string>> groupAnagramsCount(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    
    for (const string& s : strs) {
        // Create count key
        int count[26] = {0};
        for (char c : s) {
            count[c - 'a']++;
        }
        
        // Convert count to string key
        string key = "";
        for (int i = 0; i < 26; i++) {
            key += "#" + to_string(count[i]);
        }
        
        groups[key].push_back(s);
    }
    
    vector<vector<string>> result;
    for (auto& p : groups) {
        result.push_back(move(p.second));
    }
    
    return result;
}

int main() {
    vector<string> words = {"eat", "tea", "tan", "ate", "nat", "bat"};
    
    cout << "Words: [";
    for (int i = 0; i < words.size(); i++) {
        cout << "\"" << words[i] << "\"";
        if (i < words.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
    
    cout << "\nGrouped (sort method):" << endl;
    auto result = groupAnagramsSort(words);
    for (const auto& group : result) {
        cout << "  [";
        for (int i = 0; i < group.size(); i++) {
            cout << "\"" << group[i] << "\"";
            if (i < group.size() - 1) cout << ", ";
        }
        cout << "]" << endl;
    }
    
    return 0;
}

import java.util.*;

public class GroupAnagrams {
    // Group Anagrams - LeetCode 49
    // Using sorted string as key - O(n × k log k)
    static List<List<String>> groupAnagramsSort(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        
        for (String s : strs) {
            char[] arr = s.toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        
        return new ArrayList<>(groups.values());
    }
    
    // Using character count as key - O(n × k)
    static List<List<String>> groupAnagramsCount(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        
        for (String s : strs) {
            // Create count key
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            
            // Convert count to string key
            StringBuilder key = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                key.append("#").append(count[i]);
            }
            
            groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(s);
        }
        
        return new ArrayList<>(groups.values());
    }
    
    public static void main(String[] args) {
        String[] words = {"eat", "tea", "tan", "ate", "nat", "bat"};
        
        System.out.println("Words: " + Arrays.toString(words));
        
        System.out.println("\nGrouped (sort method):");
        List<List<String>> result = groupAnagramsSort(words);
        for (List<String> group : result) {
            System.out.println("  " + group);
        }
    }
}

LeetCode Practice Problems

Master these string problems for FAANG interviews:

Easy 344. Reverse String

Reverse a string in-place using \(O(1)\) extra memory.

# LeetCode 344 - Reverse String
# Time: O(n), Space: O(1)

def reverseString(s):
    """
    Reverse string in-place using two pointers.
    s is a list of characters.
    """
    left, right = 0, len(s) - 1
    
    while left < right:
        s[left], s[right] = s[right], s[left]
        left += 1
        right -= 1

s = list("hello")
reverseString(s)
print("".join(s))  # "olleh"

s = list("Hannah")
reverseString(s)
print("".join(s))  # "hannaH"

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// LeetCode 344 - Reverse String
// Time: O(n), Space: O(1)
void reverseString(vector<char>& s) {
    int left = 0, right = s.size() - 1;
    
    while (left < right) {
        swap(s[left], s[right]);
        left++;
        right--;
    }
}

int main() {
    vector<char> s = {'h', 'e', 'l', 'l', 'o'};
    reverseString(s);
    for (char c : s) cout << c;  // "olleh"
    cout << endl;
    
    return 0;
}

// LeetCode 344 - Reverse String
// Time: O(n), Space: O(1)
class Solution {
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

// Test: char[] s = {'h','e','l','l','o'};
// Result: ['o','l','l','e','h']

Easy 125. Valid Palindrome

Check if string is palindrome considering only alphanumeric characters.

# LeetCode 125 - Valid Palindrome
# Time: O(n), Space: O(1)

def isPalindrome(s):
    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].lower() != s[right].lower():
            return False
        
        left += 1
        right -= 1
    
    return True

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

#include <iostream>
#include <string>
#include <cctype>
using namespace std;

// LeetCode 125 - Valid Palindrome
// Time: O(n), Space: O(1)
bool isPalindrome(string s) {
    int left = 0, right = s.length() - 1;
    
    while (left < right) {
        while (left < right && !isalnum(s[left])) left++;
        while (left < right && !isalnum(s[right])) right--;
        
        if (tolower(s[left]) != tolower(s[right])) {
            return false;
        }
        left++;
        right--;
    }
    
    return true;
}

int main() {
    cout << boolalpha;
    cout << isPalindrome("A man, a plan, a canal: Panama") << endl;  // true
    cout << isPalindrome("race a car") << endl;  // false
    return 0;
}

// LeetCode 125 - Valid Palindrome
// Time: O(n), Space: O(1)
class Solution {
    public boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        
        while (left < right) {
            while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
                left++;
            }
            while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
                right--;
            }
            
            if (Character.toLowerCase(s.charAt(left)) != 
                Character.toLowerCase(s.charAt(right))) {
                return false;
            }
            left++;
            right--;
        }
        
        return true;
    }
}

// Test: "A man, a plan, a canal: Panama" ? true
// Test: "race a car" ? false

Medium 5. Longest Palindromic Substring

Find the longest palindromic substring in s.

# LeetCode 5 - Longest Palindromic Substring
# Time: O(n²), Space: O(1)

def longestPalindrome(s):
    def expand(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]
    
    result = ""
    for i in range(len(s)):
        # Odd length
        odd = expand(i, i)
        if len(odd) > len(result):
            result = odd
        
        # Even length
        even = expand(i, i + 1)
        if len(even) > len(result):
            result = even
    
    return result

print(longestPalindrome("babad"))  # "bab" or "aba"
print(longestPalindrome("cbbd"))   # "bb"

#include <iostream>
#include <string>
using namespace std;

// LeetCode 5 - Longest Palindromic Substring
// Time: O(n²), Space: O(1)
class Solution {
public:
    string longestPalindrome(string s) {
        int start = 0, maxLen = 1;
        
        for (int i = 0; i < s.length(); i++) {
            // Odd length
            expand(s, i, i, start, maxLen);
            // Even length
            expand(s, i, i + 1, start, maxLen);
        }
        
        return s.substr(start, maxLen);
    }
    
private:
    void expand(const string& s, int left, int right, int& start, int& maxLen) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            if (right - left + 1 > maxLen) {
                start = left;
                maxLen = right - left + 1;
            }
            left--;
            right++;
        }
    }
};

// Test: "babad" ? "bab" or "aba"
// Test: "cbbd" ? "bb"

// LeetCode 5 - Longest Palindromic Substring
// Time: O(n²), Space: O(1)
class Solution {
    int start = 0, maxLen = 1;
    
    public String longestPalindrome(String s) {
        for (int i = 0; i < s.length(); i++) {
            // Odd length
            expand(s, i, i);
            // Even length
            expand(s, i, i + 1);
        }
        
        return s.substring(start, start + maxLen);
    }
    
    private void expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && 
               s.charAt(left) == s.charAt(right)) {
            if (right - left + 1 > maxLen) {
                start = left;
                maxLen = right - left + 1;
            }
            left--;
            right++;
        }
    }
}

// Test: "babad" ? "bab" or "aba"
// Test: "cbbd" ? "bb"

Medium 49. Group Anagrams

Group strings that are anagrams of each other.

# LeetCode 49 - Group Anagrams
# Time: O(n × k), Space: O(n × k)

from collections import defaultdict

def groupAnagrams(strs):
    groups = defaultdict(list)
    
    for s in strs:
        # Use character count as key
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        groups[tuple(count)].append(s)
    
    return list(groups.values())

result = groupAnagrams(["eat","tea","tan","ate","nat","bat"])
print(result)  # [["eat","tea","ate"],["tan","nat"],["bat"]]

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

// LeetCode 49 - Group Anagrams
// Time: O(n × k), Space: O(n × k)
vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    
    for (const string& s : strs) {
        int count[26] = {0};
        for (char c : s) {
            count[c - 'a']++;
        }
        
        // Create key from count
        string key = "";
        for (int i = 0; i < 26; i++) {
            key += "#" + to_string(count[i]);
        }
        
        groups[key].push_back(s);
    }
    
    vector<vector<string>> result;
    for (auto& p : groups) {
        result.push_back(move(p.second));
    }
    
    return result;
}

// Test: ["eat","tea","tan","ate","nat","bat"]
// Result: [["eat","tea","ate"],["tan","nat"],["bat"]]

import java.util.*;

// LeetCode 49 - Group Anagrams
// Time: O(n × k), Space: O(n × k)
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        
        for (String s : strs) {
            int[] count = new int[26];
            for (char c : s.toCharArray()) {
                count[c - 'a']++;
            }
            
            // Create key from count
            StringBuilder key = new StringBuilder();
            for (int i = 0; i < 26; i++) {
                key.append("#").append(count[i]);
            }
            
            groups.computeIfAbsent(key.toString(), k -> new ArrayList<>()).add(s);
        }
        
        return new ArrayList<>(groups.values());
    }
}

// Test: ["eat","tea","tan","ate","nat","bat"]
// Result: [["eat","tea","ate"],["tan","nat"],["bat"]]

Medium 3. Longest Substring Without Repeating

Find length of longest substring without repeating characters.

# LeetCode 3 - Longest Substring Without Repeating Characters
# Sliding Window approach
# Time: O(n), Space: O(min(n, m)) where m is charset size

def lengthOfLongestSubstring(s):
    char_index = {}  # Character -> last index
    max_length = 0
    start = 0
    
    for end, char in enumerate(s):
        # If char seen and in current window
        if char in char_index and char_index[char] >= start:
            start = char_index[char] + 1
        
        char_index[char] = end
        max_length = max(max_length, end - start + 1)
    
    return max_length

print(lengthOfLongestSubstring("abcabcbb"))  # 3 ("abc")
print(lengthOfLongestSubstring("bbbbb"))     # 1 ("b")
print(lengthOfLongestSubstring("pwwkew"))    # 3 ("wke")

#include <iostream>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

// LeetCode 3 - Longest Substring Without Repeating Characters
// Sliding Window - Time: O(n), Space: O(min(n, m))
int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> charIndex;  // Character -> last index
    int maxLength = 0;
    int start = 0;
    
    for (int end = 0; end < s.length(); end++) {
        char c = s[end];
        
        // If char seen and in current window
        if (charIndex.count(c) && charIndex[c] >= start) {
            start = charIndex[c] + 1;
        }
        
        charIndex[c] = end;
        maxLength = max(maxLength, end - start + 1);
    }
    
    return maxLength;
}

int main() {
    cout << lengthOfLongestSubstring("abcabcbb") << endl;  // 3
    cout << lengthOfLongestSubstring("bbbbb") << endl;     // 1
    cout << lengthOfLongestSubstring("pwwkew") << endl;    // 3
    return 0;
}

import java.util.*;

// LeetCode 3 - Longest Substring Without Repeating Characters
// Sliding Window - Time: O(n), Space: O(min(n, m))
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> charIndex = new HashMap<>();
        int maxLength = 0;
        int start = 0;
        
        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            
            // If char seen and in current window
            if (charIndex.containsKey(c) && charIndex.get(c) >= start) {
                start = charIndex.get(c) + 1;
            }
            
            charIndex.put(c, end);
            maxLength = Math.max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }
}

// Test: "abcabcbb" ? 3 ("abc")
// Test: "bbbbb" ? 1 ("b")
// Test: "pwwkew" ? 3 ("wke")

Hard 76. Minimum Window Substring

Find minimum window in s containing all characters of t.

# LeetCode 76 - Minimum Window Substring
# Sliding Window with two pointers
# Time: O(n + m), Space: O(m)

from collections import Counter

def minWindow(s, t):
    if not t or not s:
        return ""
    
    # Count characters needed from t
    need = Counter(t)
    required = len(need)
    
    # Sliding window
    left = 0
    formed = 0
    window_counts = {}
    
    # Result: (window_length, left, right)
    result = float('inf'), None, None
    
    for right in range(len(s)):
        char = s[right]
        window_counts[char] = window_counts.get(char, 0) + 1
        
        # Check if current char satisfies requirement
        if char in need and window_counts[char] == need[char]:
            formed += 1
        
        # Contract window until it's no longer valid
        while left <= right and formed == required:
            char = s[left]
            
            # Update result
            if right - left + 1 < result[0]:
                result = (right - left + 1, left, right)
            
            # Remove left char
            window_counts[char] -= 1
            if char in need and window_counts[char] < need[char]:
                formed -= 1
            
            left += 1
    
    return "" if result[0] == float('inf') else s[result[1]:result[2] + 1]

print(minWindow("ADOBECODEBANC", "ABC"))  # "BANC"
print(minWindow("a", "a"))                # "a"
print(minWindow("a", "aa"))               # ""

#include <iostream>
#include <string>
#include <unordered_map>
#include <climits>
using namespace std;

// LeetCode 76 - Minimum Window Substring
// Sliding Window - Time: O(n + m), Space: O(m)
string minWindow(string s, string t) {
    if (s.empty() || t.empty()) return "";
    
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int required = need.size();
    int formed = 0;
    int left = 0;
    
    int minLen = INT_MAX;
    int minLeft = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s[right];
        window[c]++;
        
        if (need.count(c) && window[c] == need[c]) {
            formed++;
        }
        
        // Contract window
        while (left <= right && formed == required) {
            c = s[left];
            
            if (right - left + 1 < minLen) {
                minLen = right - left + 1;
                minLeft = left;
            }
            
            window[c]--;
            if (need.count(c) && window[c] < need[c]) {
                formed--;
            }
            
            left++;
        }
    }
    
    return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);
}

int main() {
    cout << minWindow("ADOBECODEBANC", "ABC") << endl;  // "BANC"
    cout << minWindow("a", "a") << endl;                // "a"
    cout << minWindow("a", "aa") << endl;               // ""
    return 0;
}

import java.util.*;

// LeetCode 76 - Minimum Window Substring
// Sliding Window - Time: O(n + m), Space: O(m)
class Solution {
    public String minWindow(String s, String t) {
        if (s.isEmpty() || t.isEmpty()) return "";
        
        Map<Character, Integer> need = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        
        int required = need.size();
        int formed = 0;
        int left = 0;
        
        int minLen = Integer.MAX_VALUE;
        int minLeft = 0;
        
        Map<Character, Integer> window = new HashMap<>();
        
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);
            
            if (need.containsKey(c) && 
                window.get(c).intValue() == need.get(c).intValue()) {
                formed++;
            }
            
            // Contract window
            while (left <= right && formed == required) {
                c = s.charAt(left);
                
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                }
                
                window.put(c, window.get(c) - 1);
                if (need.containsKey(c) && window.get(c) < need.get(c)) {
                    formed--;
                }
                
                left++;
            }
        }
        
        return minLen == Integer.MAX_VALUE ? "" : 
               s.substring(minLeft, minLeft + minLen);
    }
}

// Test: "ADOBECODEBANC", "ABC" ? "BANC"

Next in the Series

In Part 5: Matrices, we’ll extend arrays into two dimensions with matrices — covering sparse representations, special matrices, and the traversal patterns that appear in graph and DP problems.

Table of Contents

FAANG Interview Prep

Foundations, Memory & Complexity

Recursion Complete Guide

Arrays & Array ADT

Strings

Matrices

Linked Lists

Stack

Queue

Trees

BST & Balanced Trees

Heaps, Sorting & Hashing

Graphs, DP, Greedy & Backtracking

String Fundamentals