Strings — Complete DSA String Theory

Learning Progress. Work top to bottom: theory → operations → the interactive visualizer → patterns → cheat sheet → interview prep. Pin the visualizer (button top-right of the panel) to keep it on screen while you read.

Theory & Fundamentals

What is a String?

A String is a sequence of characters, stored as a contiguous array of code units. In C it's null-terminated ('\0'); in C++ std::string tracks its own length and grows dynamically.

Because it's an array under the hood, indexed access is O(1), but insertion/deletion in the middle is O(n) and (in many languages) strings are immutable, so edits create new strings.

Layout

// "hello" as a char array
Index: 0 1 2 3 4 5
Char: h e l l o \0

// s[i] = base + i * sizeof(char)
char c = s[1]; // 'e' — O(1)

Why Strings matter. Text is everywhere: parsing, search, tokenization, DNA sequences, URLs, JSON. String problems dominate interviews because they combine arrays, hashing, two pointers, sliding windows, and DP.

Key techniques

↔️

Two Pointers

Pointers from both ends (palindrome, reverse) or same direction (dedup).

Use: palindrome, reverse, compare.

🪟

Sliding Window

Expand/contract a window over the string tracking a frequency condition.

Use: longest substring, anagrams, min window.

🔤

Frequency / Hashing

Count characters in an int[26]/int[128] array or hash map.

Use: anagrams, first unique char, ransom note.

🔎

Pattern Matching

KMP prefix function, Rabin-Karp hashing, Z-algorithm.

Use: substring search in O(n+m).

🧮

Dynamic Programming

2D DP over indices for edit distance, LCS, palindrome partition.

Use: edit distance, LCS, regex match.

🌲

Trie

Prefix tree of characters for fast multi-word prefix queries.

Use: autocomplete, word search, dictionary.

Terminology

Substring

A contiguous slice of the string, s[i..j].

Subsequence

Characters kept in order but not necessarily contiguous.

Prefix / Suffix

A leading / trailing substring. Central to KMP and tries.

Palindrome

Reads the same forwards and backwards.

Anagram

A rearrangement of the same character multiset.

Immutability

In Java/Python, edits create a new string; C++ string is mutable.

Complexity Summary

Access s[i]

O(1)

Direct index into the char array.

Concatenation

O(n+m)

Copies both strings into a new buffer.

Substring search

O(n+m)

KMP / Z / Rabin-Karp.

Reverse

O(n)

Two pointers, in-place for mutable strings.

Sort chars

O(n log n)

O(n) with counting sort for small alphabet.

Edit distance

O(n·m)

2D DP over both strings.

Advantages & Disadvantages

Advantages

O(1) indexed character access.
Rich STL API (find, substr, compare, replace).
Fits every classic pattern: two pointers, windows, hashing, DP.
Small fixed alphabet enables O(n) counting tricks.

Disadvantages

Immutability (Java/Python) makes naive concatenation O(n²).
Middle insert/delete is O(n).
Unicode/encoding pitfalls: a "character" may be multiple code units.
Pattern matching needs care to avoid O(n·m) brute force.

C++ STL Implementation

string_basics.cpp · std::string essentials

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s = "hello world";
    cout << s.size() << "\n";          // 11
    cout << s[0] << "\n";               // 'h' — O(1)
    cout << s.substr(6) << "\n";        // "world"
    cout << s.find("world") << "\n";   // 6
    reverse(s.begin(), s.end());     // in-place O(n)
    sort(s.begin(), s.end());          // sort chars
    // frequency count
    int freq[26] = {0};
    for (char c : s) if (c >= 'a' && c <= 'z') freq[c - 'a']++;
    return 0;
}

patterns.cpp · Palindrome, anagram, sliding window

// Palindrome — two pointers O(n)
bool isPalindrome(string s) {
    int i = 0, j = s.size() - 1;
    while (i < j) if (s[i++] != s[j--]) return false;
    return true;
}

// Valid anagram — frequency O(n)
bool isAnagram(string a, string b) {
    if (a.size() != b.size()) return false;
    int f[26] = {0};
    for (char c : a) f[c - 'a']++;
    for (char c : b) if (--f[c - 'a'] < 0) return false;
    return true;
}

// Longest substring w/o repeating — sliding window O(n)
int lengthOfLongest(string s) {
    vector<int> last(128, -1);
    int left = 0, best = 0;
    for (int r = 0; r < s.size(); r++) {
        if (last[s[r]] >= left) left = last[s[r]] + 1;
        last[s[r]] = r;
        best = max(best, r - left + 1);
    }
    return best;
}

Interactive String Visualization

Char Pointer i Pointer j Window Match Mismatch

Idle

Current operation details

Operation

—

Pointer(s)

—

Best / Result

—

Steps

taken

Comparisons

checks

Window len

current

Length

chars

Step — of —

Select a scenario above, or use the manual controls, then press Play.

Manual controls — enter your own string

String: Pattern/char:

✓ Done

Speed

Step-by-step operation log

Step	i	j	Action	State
Run a scenario to populate the log.

Key Patterns

Sliding window. Expand the right edge to include a new char; when the window breaks the condition (repeat char, too many distinct), shrink from the left. Track the best window length. Most "longest/shortest substring" problems are O(n) this way.

Frequency arrays beat hash maps for fixed alphabets. An int[26] or int[128] is faster and simpler than a hash map for lowercase/ASCII problems — anagrams, first unique char, ransom note.

Cheat Sheet

Task	Technique	Time	Notes
Palindrome check	Two pointers	O(n)	Compare ends inward
Reverse	Two pointers	O(n)	Swap in place
Anagram	Frequency array	O(n)	int[26] counts
Longest substring	Sliding window	O(n)	Expand/contract
Substring search	KMP / Z	O(n+m)	Prefix function
Edit distance / LCS	2D DP	O(n·m)	Tabulation

Learning Roadmap

String Basics

std::string API, indexing, substr, find, immutability vs mutability.

~2 hours

Two Pointers & Frequency

Palindrome, reverse, anagram, first unique char, valid palindrome II.

~3 hours

Sliding Window

Longest substring without repeats, min window substring, find all anagrams.

~4 hours

Pattern Matching

KMP prefix function, Z-algorithm, Rabin-Karp rolling hash.

~4 hours

String DP

Edit distance, longest common subsequence, palindromic substrings, regex matching.

~4 hours

Interview Preparation

Valid Palindrome

Two pointers from both ends, skip non-alphanumerics, compare case-insensitively. O(n)/O(1).

Two Pointers

Longest Substring Without Repeating

Sliding window with last-seen index array; jump left past the repeat. O(n).

Window

Group Anagrams

Key each word by its sorted form (or char-count signature) into a hash map. O(n·k log k).

Hashing

Minimum Window Substring

Two frequency maps (need/have) and a shrinking window once all chars are covered. O(n).

Window

Practice Problems

EasyValid PalindromeTwo Pointers

EasyValid AnagramFrequency

EasyReverse StringTwo Pointers

MediumLongest Substring Without RepeatingWindow

MediumGroup AnagramsHashing

MediumLongest Palindromic SubstringExpand Center

HardMinimum Window SubstringWindow

HardEdit DistanceDP

Key Takeaways

🔤Strings are char arrays: O(1) index, O(n) middle edits, often immutable — avoid naive concatenation in loops.

🪟Sliding window: the workhorse for "longest/shortest substring" problems, turning O(n²) into O(n).

🔢Frequency arrays: int[26]/int[128] beats a hash map for fixed alphabets — anagrams, uniqueness, counting.

🔎Pattern matching & DP: KMP/Z for search in O(n+m); 2D DP for edit distance, LCS, and regex.