๐ค Strings
One-line summary: Immutable character sequences โ master sliding window, two pointers, and hashing on strings for O(n) solutions to substring/pattern problems.
๐ Visual Learningโ
String Processing Techniquesโ
Visualization of sliding window technique for substring problems and pattern matching
String Algorithm Animationsโ
Interactive demonstration of string manipulation algorithms and optimization techniques
Two Pointers on Stringsโ
Visual guide to using two pointers for palindrome checking and string reversal
String Hashing Visualizationโ
Understanding how string hashing works for fast substring search and pattern matching
๐ฏ Core Conceptsโ
String Fundamentalsโ
- Immutability: Strings in JavaScript are immutable โ operations create new strings
- Character Access: Use
s[i]ors.charAt(i)to access characters - Length:
s.lengthgives the number of characters - Conversion:
s.split('')converts string to character array for manipulation
Essential String Operationsโ
// Basic operations
s.charAt(i); // Get character at index i
s.charCodeAt(i); // Get ASCII/Unicode value
String.fromCharCode(c); // Convert ASCII to character
s.slice(start, end); // Extract substring
s.substring(start, end); // Similar to slice
s.indexOf(substr); // Find first occurrence
s.toLowerCase(); // Convert to lowercase
s.toUpperCase(); // Convert to uppercase
โก Common Operation Complexityโ
| Operation | Time | Space |
|---|---|---|
Access s[i] | O(1) | O(1) |
Concatenation a + b | O(n + m) | O(n + m) |
slice / substring | O(k) | O(k) |
indexOf (naive search) | O(nยทm) | O(1) |
| Reverse | O(n) | O(n) |
| Sort characters | O(n log n) | O(n) |
| Frequency map build | O(n) | O(1) (fixed alphabet) |
โ ๏ธ Strings are immutable in JS โ building a string in a loop with
+=is O(nยฒ). Use an array +join('')for O(n).
Key String Patternsโ
- Anagram Detection: Sort characters or use frequency counting
- Palindrome Check: Two pointers from ends moving inward
- Substring Search: Sliding window or KMP algorithm
- Pattern Matching: Regular expressions or manual parsing
When to Use String Algorithms?โ
โ Use when you need:
- Text processing and manipulation
- Pattern matching and searching
- Anagram or palindrome detection
- Substring operations
- Character frequency analysis
โ Avoid when:
- Working with purely numerical data
- Simple boolean operations
- Array manipulations without text context
๐งฉ String Algorithm Toolkitโ
Most string problems reduce to one of a handful of patterns. Pick the right tool:
flowchart TD
A["String problem"] --> B{"Contiguous\nsubstring?"}
B -->|Yes, fixed/variable window| C["Sliding Window"]
B -->|Palindrome / from both ends| D["Two Pointers"]
A --> E{"Pattern search\nin text?"}
E -->|Single pattern| F["KMP O(n+m)"]
E -->|Multiple / rolling compare| G["Rabin-Karp O(n+m) avg"]
A --> H{"Frequency /\nanagram?"}
H -->|Yes| I["Hashing / Freq Map"]
| Technique | Use Case | Time | Space | Cross-link |
|---|---|---|---|---|
| Two Pointers | Palindromes, reversal | O(n) | O(1) | Two Pointers |
| Sliding Window | Longest/shortest substring with constraint | O(n) | O(k) | Sliding Window |
| Hashing / Freq Map | Anagrams, char counts | O(n) | O(1) (26 letters) | Hashing |
| KMP | Single-pattern search | O(n + m) | O(m) | โ |
| Rabin-Karp | Rolling-hash pattern search | O(n + m) avg | O(1) | โ |
KMP โ Knuth-Morris-Pratt (linear pattern matching)โ
function kmpSearch(text, pattern) {
const lps = buildLPS(pattern); // longest proper prefix that is also suffix
let i = 0,
j = 0;
while (i < text.length) {
if (text[i] === pattern[j]) {
i++;
j++;
}
if (j === pattern.length)
return i - j; // match found
else if (i < text.length && text[i] !== pattern[j]) {
j = j > 0 ? lps[j - 1] : 0; // skip using LPS table
if (j === 0 && text[i] !== pattern[0]) i++;
}
}
return -1;
}
function buildLPS(p) {
const lps = new Array(p.length).fill(0);
let len = 0,
i = 1;
while (i < p.length) {
if (p[i] === p[len]) lps[i++] = ++len;
else if (len > 0) len = lps[len - 1];
else lps[i++] = 0;
}
return lps;
}
// Time: O(n + m), Space: O(m). Never re-examines text characters.
Rabin-Karp โ rolling hash searchโ
function rabinKarp(text, pattern) {
const base = 256,
mod = 1_000_000_007;
const m = pattern.length,
n = text.length;
if (m > n) return -1;
let patHash = 0,
winHash = 0,
pow = 1;
for (let i = 0; i < m; i++) {
patHash = (patHash * base + pattern.charCodeAt(i)) % mod;
winHash = (winHash * base + text.charCodeAt(i)) % mod;
if (i < m - 1) pow = (pow * base) % mod;
}
for (let i = 0; i + m <= n; i++) {
if (patHash === winHash && text.substr(i, m) === pattern) return i;
if (i + m < n) {
winHash =
((winHash - ((text.charCodeAt(i) * pow) % mod) + mod) * base + text.charCodeAt(i + m)) %
mod;
}
}
return -1;
}
// Avg O(n + m); rolling hash updates the window in O(1).
๏ฟฝ String Algorithms Referenceโ
The following string algorithms live as runnable implementations (with tests) in this folder. Each entry preserves the full reference notes merged from the former concepts/string collection.
Hamming Distanceโ
๐ Implementation:
hamming-distance/ยท Tests:hamming-distance/__test__
The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of substitutions required to change one string into the other, or the minimum number of errors that could have transformed one string into the other. In a more general context, the Hamming distance is one of several string metrics for measuring the edit distance between two sequences.
Examples
The Hamming distance between:
- "karolin" and "kathrin" is 3.
- "karolin" and "kerstin" is 3.
- 1011101 and 1001001 is 2.
- 2173896 and 2233796 is 3.
References
KnuthโMorrisโPratt Algorithmโ
๐ Implementation:
knuth-morris-pratt/ยท Tests:knuth-morris-pratt/__test__
The KnuthโMorrisโPratt string searching algorithm (or KMP algorithm) searches for occurrences of a "word" W within a main "text string" T by employing the observation that when a mismatch occurs, the word itself embodies sufficient information to determine where the next match could begin, thus bypassing re-examination of previously matched characters.
Complexity
- Time:
O(|W| + |T|)(much faster comparing to trivialO(|W| * |T|)) - Space:
O(|W|)
References
Levenshtein Distanceโ
๐ Implementation:
levenshtein-distance/ยท Tests:levenshtein-distance/__test__
The Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other.
Definition
Mathematically, the Levenshtein distance between two strings a and b (of length |a| and |b| respectively) is given by
where
0 when
i characters of a and the first j characters of b.
Note that the first element in the minimum corresponds to deletion (from a to b), the second to insertion and the third to match or mismatch, depending on whether the respective symbols are the same.
Example
For example, the Levenshtein distance between kitten and sitting is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:
- kitten โ sitten (substitution of "s" for "k")
- sitten โ sittin (substitution of "i" for "e")
- sittin โ sitting (insertion of "g" at the end).
Applications
This has a wide range of applications, for instance, spell checkers, correction systems for optical character recognition, fuzzy string searching, and software to assist natural language translation based on translation memory.
Dynamic Programming Approach Explanation
Letโs take a simple example of finding minimum edit distance between strings ME and MY. Intuitively you already know that minimum edit distance here is 1 operation, which is replacing E with Y. But letโs try to formalize it in a form of the algorithm in order to be able to do more complex examples like transforming Saturday into Sunday.
To apply the mathematical formula mentioned above to ME โ MY transformation we need to know minimum edit distances of ME โ M, M โ MY and M โ M transformations in prior. Then we will need to pick the minimum one and add one operation to transform last letters E โ Y. So minimum edit distance of ME โ MY transformation is being calculated based on three previously possible transformations.
To explain this further letโs draw the following matrix:
- Cell
(0:1)contains red number 1. It means that we need 1 operation to transformMto an empty string. And it is by deletingM. This is why this number is red. - Cell
(0:2)contains red number 2. It means that we need 2 operations to transformMEto an empty string. And it is by deletingEandM. - Cell
(1:0)contains green number 1. It means that we need 1 operation to transform an empty string toM. And it is by insertingM. This is why this number is green. - Cell
(2:0)contains green number 2. It means that we need 2 operations to transform an empty string toMY. And it is by insertingYandM. - Cell
(1:1)contains number 0. It means that it costs nothing to transformMintoM. - Cell
(1:2)contains red number 1. It means that we need 1 operation to transformMEtoM. And it is by deletingE. - And so on...
This looks easy for such small matrix as ours (it is only 3x3). But here you may find basic concepts that may be applied to calculate all those numbers for bigger matrices (letโs say a 9x7 matrix for Saturday โ Sunday transformation).
According to the formula you only need three adjacent cells (i-1:j), (i-1:j-1), and (i:j-1) to calculate the number for current cell (i:j). All we need to do is to find the minimum of those three cells and then add 1 in case if we have different letters in i's row and j's column.
You may clearly see the recursive nature of the problem.
Let's draw a decision graph for this problem.
You may see a number of overlapping sub-problems on the picture that are marked with red. Also there is no way to reduce the number of operations and make it less than a minimum of those three adjacent cells from the formula.
Also you may notice that each cell number in the matrix is being calculated based on previous ones. Thus the tabulation technique (filling the cache in bottom-up direction) is being applied here.
Applying this principle further we may solve more complicated cases like with Saturday โ Sunday transformation.
References
Longest Common Substring Problemโ
๐ Implementation:
longest-common-substring/ยท Tests:longest-common-substring/__test__
The longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two or more strings.
Example
The longest common substring of the strings ABABC, BABCA and ABCBA is string ABC of length 3. Other common substrings are A, AB, B, BA, BC and C.
ABABC
|||
BABCA
|||
ABCBA
References
Palindrome Checkโ
๐ Implementation:
palindrome/ยท Tests:palindrome/__test__
A Palindrome is a string that reads the same forwards and backwards. This means that the second half of the string is the reverse of the first half.
Examples
The following are palindromes (thus would return TRUE):
- "a"
- "pop" -> p + o + p
- "deed" -> de + ed
- "kayak" -> ka + y + ak
- "racecar" -> rac + e + car
The following are NOT palindromes (thus would return FALSE):
- "rad"
- "dodo"
- "polo"
References
Rabin Karp Algorithmโ
๐ Implementation:
rabin-karp/ยท Tests:rabin-karp/__test__
In computer science, the RabinโKarp algorithm or KarpโRabin algorithm is a string searching algorithm created by Richard M. Karp and Michael O. Rabin (1987) that uses hashing to find any one of a set of pattern strings in a text.
Algorithm
The RabinโKarp algorithm seeks to speed up the testing of equality of the pattern to the substrings in the text by using a hash function. A hash function is a function which converts every string into a numeric value, called its hash value; for example, we might have hash('hello') = 5. The algorithm exploits the fact that if two strings are equal, their hash values are also equal. Thus, string matching is reduced (almost) to computing the hash value of the search pattern and then looking for substrings of the input string with that hash value.
However, there are two problems with this approach. First, because there are so many different strings and so few hash values, some differing strings will have the same hash value. If the hash values match, the pattern and the substring may not match; consequently, the potential match of search pattern and the substring must be confirmed by comparing them; that comparison can take a long time for long substrings. Luckily, a good hash function on reasonable strings usually does not have many collisions, so the expected search time will be acceptable.
Hash Function Used
The key to the RabinโKarp algorithm's performance is the efficient computation of hash values of the successive substrings of the text. The Rabin fingerprint is a popular and effective rolling hash function.
The polynomial hash function described in this example is not a Rabin fingerprint, but it works equally well. It treats every substring as a number in some base, the base being usually a large prime.
Complexity
For text of length n and p patterns of combined length m, its average and best case running time is O(n + m) in space O(p), but its worst-case time is O(n * m).
Application
A practical application of the algorithm is detecting plagiarism. Given source material, the algorithm can rapidly search through a paper for instances of sentences from the source material, ignoring details such as case and punctuation. Because of the abundance of the sought strings, single-string searching algorithms are impractical.
References
Regular Expression Matchingโ
๐ Implementation:
regular-expression-matching/ยท Tests:regular-expression-matching/__test__
Given an input string s and a pattern p, implement regular expression matching with support for . and *.
.Matches any single character.*Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note
scould be empty and contains only lowercase lettersa-z.pcould be empty and contains only lowercase lettersa-z, and characters like.or*.
Examples
Example #1
Input:
s = 'aa'
p = 'a'
Output: false
Explanation: a does not match the entire string aa.
Example #2
Input:
s = 'aa'
p = 'a*'
Output: true
Explanation: * means zero or more of the preceding element, a. Therefore, by repeating a once, it becomes aa.
Example #3
Input:
s = 'ab'
p = '.*'
Output: true
Explanation: .* means "zero or more (*) of any character (.)".
Example #4
Input:
s = 'aab'
p = 'c*a*b'
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches aab.
References
Z Algorithmโ
๐ Implementation:
z-algorithm/ยท Tests:z-algorithm/__test__
The Z-algorithm finds occurrences of a "word" W within a main "text string" T in linear time O(|W| + |T|).
Given a string S of length n, the algorithm produces an array, Z where Z[i] represents the longest substring starting from S[i] which is also a prefix of S. Finding Z for the string obtained by concatenating the word, W with a nonce character, say $ followed by the text, T, helps with pattern matching, for if there is some index i such that Z[i] equals the pattern length, then the pattern must be present at that point.
While the Z array can be computed with two nested loops in O(|W| * |T|) time, the following strategy shows how to obtain it in linear time, based on the idea that as we iterate over the letters in the string (index i from 1 to n - 1), we maintain an interval [L, R] which is the interval with maximum R such that 1 โค L โค i โค R and S[L...R] is a prefix that is also a substring (if no such interval exists, just let L = R = - 1). For i = 1, we can simply compute L and R by comparing S[0...] to S[1...].
Example of Z array
Index 0 1 2 3 4 5 6 7 8 9 10 11
Text a a b c a a b x a a a z
Z values X 1 0 0 3 1 0 0 2 2 1 0
Other examples
str = a a a a a a
Z[] = x 5 4 3 2 1
str = a a b a a c d
Z[] = x 1 0 2 1 0 0
str = a b a b a b a b
Z[] = x 0 6 0 4 0 2 0
Example of Z box
Complexity
- Time:
O(|W| + |T|) - Space:
O(|W|)
References
๏ฟฝ๐ง Essential Patterns & Templatesโ
1๏ธโฃ Anagram Detection - Two Approachesโ
Method 1: Sorting (Simple but O(n log n))
function isAnagram(s, t) {
if (s.length !== t.length) return false;
return s.split('').sort().join('') === t.split('').sort().join('');
}
// Time: O(n log n), Space: O(n)
// Use case: Simple anagram check
Method 2: Frequency Count (Optimal O(n))
function isAnagram(s, t) {
if (s.length !== t.length) return false;
const freq = {};
// Count characters in first string
for (const char of s) {
freq[char] = (freq[char] || 0) + 1;
}
// Decrement for second string
for (const char of t) {
if (!freq[char]) return false;
freq[char]--;
}
return true;
}
// Time: O(n), Space: O(1) - at most 26 letters
2๏ธโฃ Palindrome Check - Two Pointersโ
function isPalindrome(s) {
// Clean string: remove non-alphanumeric, convert to lowercase
const cleaned = s.replace(/[^a-zA-Z0-9]/g, '').toLowerCase();
let left = 0,
right = cleaned.length - 1;
while (left < right) {
if (cleaned[left] !== cleaned[right]) return false;
left++;
right--;
}
return true;
}
// Time: O(n), Space: O(1)
// Use case: Valid palindrome problems
3๏ธโฃ Sliding Window - Longest Substring Without Repeating Charactersโ
function lengthOfLongestSubstring(s) {
const charSet = new Set();
let left = 0,
maxLength = 0;
for (let right = 0; right < s.length; right++) {
// Shrink window until no duplicates
while (charSet.has(s[right])) {
charSet.delete(s[left]);
left++;
}
charSet.add(s[right]);
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
// Time: O(n), Space: O(min(m,n)) where m is charset size
// Use case: Substring problems with constraints
4๏ธโฃ String Matching - KMP Algorithm Previewโ
function strStr(haystack, needle) {
if (needle.length === 0) return 0;
if (needle.length > haystack.length) return -1;
// Simple approach - for KMP, build failure function
for (let i = 0; i <= haystack.length - needle.length; i++) {
if (haystack.substring(i, i + needle.length) === needle) {
return i;
}
}
return -1;
}
// Time: O(n*m) simple, O(n+m) with KMP
// Use case: Pattern matching, substring search
5๏ธโฃ Character Frequency Mapโ
function getCharFrequency(s) {
const freq = new Map();
for (const char of s) {
freq.set(char, (freq.get(char) || 0) + 1);
}
return freq;
}
// Use case: Anagrams, character analysis, permutations
โ ๏ธ Common Pitfalls & How to Avoid Themโ
๐ซ Performance Pitfallsโ
// โ Wrong - O(nยฒ) string concatenation in loop
let result = '';
for (let i = 0; i < arr.length; i++) {
result += arr[i]; // Creates new string each time!
}
// โ
Correct - O(n) using array join
const parts = [];
for (let i = 0; i < arr.length; i++) {
parts.push(arr[i]);
}
const result = parts.join('');
๐ซ Character Access Confusionโ
// Both work in modern JavaScript
const char1 = str[i]; // โ
Preferred - cleaner syntax
const char2 = str.charAt(i); // โ
Safe - returns '' for invalid index
// Key difference:
str[999]; // undefined for out-of-bounds
str.charAt(999); // '' (empty string) for out-of-bounds
๐ซ Unicode and Emoji Issuesโ
const text = 'Hello ๐ World';
console.log(text.length); // 13 (not 12!) - emoji counts as 2
// โ
For proper character counting with Unicode:
const properLength = [...text].length; // 12 - correct count
๐ซ Case Sensitivity Mistakesโ
// โ Wrong - case sensitive comparison
if (str1 === str2) { ... }
// โ
Correct - case insensitive when needed
if (str1.toLowerCase() === str2.toLowerCase()) { ... }
๐ซ Boundary Conditionsโ
// Always check for:
// - Empty strings
// - Single character strings
// - Null or undefined inputs
function safeStringOperation(s) {
if (!s || s.length === 0) return '';
// ... rest of logic
}
๐ก Pro Tipsโ
- Use
String.prototype.includes()for substring checking - Remember that
slice()can take negative indices - Use template literals for complex string building
- Consider regex for complex pattern matching
- Use
split()andjoin()for character manipulation
Practice Problemsโ
๐ Related Topicsโ
- Sliding Window โ Essential for substring problems
- Two Pointers โ Palindrome and string reversal
- Hashing โ Character frequency and anagram detection
- Dynamic Programming โ Edit distance and string matching
- Backtracking โ String permutations and combinations
๐ฏ Quick Interview Prep Checklistโ
- Master anagram detection (both sorting and frequency methods)
- Understand palindrome checking with two pointers
- Practice sliding window for substring problems
- Know string manipulation techniques (reverse, rotate)
- Comfortable with character frequency counting
- Understand basic pattern matching algorithms
- Practice string parsing and validation
- Know when to use StringBuilder pattern (array + join)
โ Back to Home ยท ยฉ sparshjaswal