DSA Part 4: Strings

String Fundamentals

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 Representation

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

Python

# 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!

C++

#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;
}

Java

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

Python

# 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'

C++

#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;
}

Java

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

Python

# 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!")

C++

#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;
}

Java

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.

Naive (Brute Force) Algorithm

Python

# 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)]}")

C++

#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;
}

Java

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 improves on naive search by avoiding re-examination of matched characters. It preprocesses the pattern to build a "failure function" (LPS array).

Python

# 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}")

C++

#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;
}

Java

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 hashing to find pattern matches. It's particularly useful for multiple pattern search and plagiarism detection.

Python

# 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}")

C++

#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;
}

Java

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

Palindrome Algorithms

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

Python

# 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')}")

C++

#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;
}

Java

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.

Python

# 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

C++

#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;
}

Java

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!

Python

# 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}")

C++

#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;
}

Java

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

Python

# 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}")

C++

#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;
}

Java

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:

# 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']

# 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

# 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"

# 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"]]

# 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")

# 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"