String Manipulation: Code Templates in 6 Languages
If you have not read the concept guide yet, start there for the intuition and complexity analysis. This page gives you the code you can memorize and adapt during an interview. Every template here follows the string handling rules from the concept page: no repeated concatenation, explicit normalization, and verification of hash matches.
Main Template: Expand Around Center
This is the workhorse for palindrome problems. Instead of checking every substring as a candidate, you treat each position as a potential center and expand outward while the edges match. It solves Longest Palindromic Substring directly and adapts to counting problems like Palindromic Substrings .
var longestPalindrome = function(s) {
const expand = (left, right) => {
// Grow the window while the two edges still match.
// A mismatch or a walk off the string ends the expansion.
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return s.substring(left + 1, right);
};
let best = "";
for (let i = 0; i < s.length; i++) {
// Odd-length palindromes center on one character,
// even-length ones center between two characters.
const odd = expand(i, i);
const even = expand(i, i + 1);
if (odd.length > best.length) best = odd;
if (even.length > best.length) best = even;
}
return best;
};Code Breakdown
Key Variables
left/right: the two edges of the current expansion window. They start at the center and move outward, so they define the bounds of the palindrome being tested.best: the longest palindrome found so far. It only changes when a longer expansion comes back.odd/even: the two expansion results for each center. The odd expansion treats positionias the center of an odd-length palindrome. The even expansion treats the gap betweeniandi + 1as the center of an even-length one.
Visual Mechanism
graph TD
A["For each center i"] --> B["Expand from (i, i)"]
A --> C["Expand from (i, i + 1)"]
B --> D{"Edges match?"}
C --> E{"Edges match?"}
D -->|"Yes"| D2["Widen both edges"]
D2 --> D
E -->|"Yes"| E2["Widen both edges"]
E2 --> E
D -->|"No"| F["Record window if longest"]
E -->|"No"| G["Record window if longest"]
F --> H["Next center"]
G --> H
H --> A
Critical Sections
The expansion loop is the whole algorithm. It widens the window while the two edge characters match, and stops on the first mismatch or when a pointer walks off the string. Because the loop stops one step past the mismatch, the returned slice starts at left + 1 and ends before right.
The two center types matter. Odd-length palindromes have one center character, so they expand from (i, i). Even-length palindromes have a center between two characters, so they expand from (i, i + 1). Skipping the even case misses every palindrome with an even length, which is the most common bug in this template.
The comparison uses > when recording best, so the first longest palindrome wins. That detail does not change the answer for length queries, but it matters when the problem asks for any valid substring.
Variations
1. Frequency Counting (Anagram Check)
Two strings are anagrams when they have the same character counts. A single dictionary can verify this in one pass per string, without sorting either input.
Use this for First Unique Character in a String .
var isAnagram = function(s, t) {
if (s.length !== t.length) return false;
const count = {};
// Add every character of s, then consume every
// character of t. A negative count means t has a
// character s does not have, or has too many of one.
for (const c of s) count[c] = (count[c] || 0) + 1;
for (const c of t) {
count[c] = (count[c] || 0) - 1;
if (count[c] < 0) return false;
}
return true;
};2. Rolling Hash (Rabin-Karp)
Substring search gets fast when each window hash is derived from the previous one instead of recomputed. The hash slides one character at a time, and a hash match is always confirmed by a direct comparison.
Use this for Longest Duplicate Substring .
function rabinKarp(text, pattern) {
const n = text.length, m = pattern.length;
if (m > n) return -1;
const base = 31, mod = 1000000007;
let patternHash = 0, windowHash = 0, power = 1;
for (let i = 0; i < m; i++) {
patternHash = (patternHash * base + pattern.charCodeAt(i)) % mod;
windowHash = (windowHash * base + text.charCodeAt(i)) % mod;
power = (power * base) % mod;
}
if (patternHash === windowHash && text.slice(0, m) === pattern) return 0;
for (let i = 1; i <= n - m; i++) {
// Drop the character leaving the window and add
// the one entering it, reusing the previous hash.
windowHash = ((windowHash * base
- text.charCodeAt(i - 1) * power
+ text.charCodeAt(i + m - 1)) % mod + mod) % mod;
// A hash match can still be a collision,
// so verify the actual characters.
if (windowHash === patternHash && text.slice(i, i + m) === pattern) return i;
}
return -1;
}3. KMP Prefix Function
KMP preprocesses the pattern into a prefix table, then scans the text once. On a mismatch, the table says how far back to fall instead of restarting the scan at the next position.
Use this for Shortest Palindrome .
function kmpSearch(text, pattern) {
const m = pattern.length;
if (m === 0) return 0;
// pi[i] is the length of the longest proper prefix
// of pattern[0..i] that is also a suffix. After a
// mismatch, this is how far back the match can restart.
const pi = new Array(m).fill(0);
let j = 0;
for (let i = 1; i < m; i++) {
while (j > 0 && pattern[i] !== pattern[j]) j = pi[j - 1];
if (pattern[i] === pattern[j]) j++;
pi[i] = j;
}
j = 0;
for (let i = 0; i < text.length; i++) {
while (j > 0 && text[i] !== pattern[j]) j = pi[j - 1];
if (text[i] === pattern[j]) j++;
if (j === m) return i - m + 1;
}
return -1;
}Now head to the practice problems to apply these templates to real interview questions.