In JavaScript, strings are immutable, so convert to an array, reverse, and join back.
function reverseString(str) {
return str.split('').reverse().join('');
}
// reverseString("hello") => "olleh"
// Two-pointer approach:
function reverseStr(str) {
const arr = str.split('');
let l = 0, r = arr.length - 1;
while (l < r) {
[arr[l], arr[r]] = [arr[r], arr[l]];
l++; r--;
}
return arr.join('');
}
Time: O(n) | Space: O(n)
A palindrome reads the same forwards and backwards. Compare characters from both ends moving inward.
function isPalindrome(str) {
str = str.toLowerCase().replace(/[^a-z0-9]/g, '');
let left = 0, right = str.length - 1;
while (left < right) {
if (str[left] !== str[right]) return false;
left++;
right--;
}
return true;
}
// isPalindrome("racecar") => true
// isPalindrome("A man, a plan, a canal: Panama") => true
Time: O(n) | Space: O(1) (excluding the cleaned string)
Two strings are anagrams if they contain the same characters with the same frequency. Use a frequency map.
function isAnagram(s, t) {
if (s.length !== t.length) return false;
const freq = {};
for (const ch of s) freq[ch] = (freq[ch] || 0) + 1;
for (const ch of t) {
if (!freq[ch]) return false;
freq[ch]--;
}
return true;
}
// isAnagram("listen", "silent") => true
// isAnagram("hello", "world") => false
Time: O(n) | Space: O(1) — at most 26 lowercase letters.
Count character frequencies first, then find the first character with a count of 1.
function firstNonRepeating(str) {
const freq = {};
for (const ch of str) freq[ch] = (freq[ch] || 0) + 1;
for (const ch of str) {
if (freq[ch] === 1) return ch;
}
return null;
}
// firstNonRepeating("aabcbd") => "c"
// firstNonRepeating("aabb") => null
Time: O(n) | Space: O(1) — bounded by character set size.
String compression replaces consecutive repeated characters with the character and its count (e.g., "aaabbc" → "a3b2c1").
function compress(str) {
let result = '';
let count = 1;
for (let i = 0; i < str.length; i++) {
if (str[i] === str[i + 1]) {
count++;
} else {
result += str[i] + count;
count = 1;
}
}
return result.length < str.length ? result : str;
}
// compress("aaabbc") => "a3b2c1"
// compress("abc") => "abc" (no compression benefit)
Time: O(n) | Space: O(n)
Iterate through the string and check each character against a set of vowels.
function countVowels(str) {
const vowels = new Set('aeiouAEIOU');
let count = 0;
for (const ch of str) {
if (vowels.has(ch)) count++;
}
return count;
}
// countVowels("Hello World") => 3
// countVowels("aEiOu") => 5
Time: O(n) | Space: O(1)
Use the sliding window technique with a Set to track characters in the current window.
function longestUniqueSubstring(s) {
const set = new Set();
let left = 0, maxLen = 0;
for (let right = 0; right < s.length; right++) {
while (set.has(s[right])) {
set.delete(s[left]);
left++;
}
set.add(s[right]);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// longestUniqueSubstring("abcabcbb") => 3 ("abc")
// longestUniqueSubstring("pwwkew") => 3 ("wke")
Time: O(n) | Space: O(min(n, charset))
The naive approach slides a window of length m over the string of length n and checks for a match at each position.
function findSubstring(text, pattern) {
for (let i = 0; i <= text.length - pattern.length; i++) {
let j = 0;
while (j < pattern.length && text[i + j] === pattern[j]) {
j++;
}
if (j === pattern.length) return i;
}
return -1;
}
// findSubstring("hello world", "world") => 6
// findSubstring("abcdef", "xyz") => -1
Time: O(n × m) worst case. Optimized algorithms like KMP achieve O(n + m).
Split the string by spaces, capitalize the first character of each word, then join back.
function capitalizeWords(str) {
return str
.split(' ')
.map(word =>
word.charAt(0).toUpperCase() + word.slice(1).toLowerCase()
)
.join(' ');
}
// capitalizeWords("hello world foo") => "Hello World Foo"
// capitalizeWords("javaScript is FUN") => "Javascript Is Fun"
Time: O(n) | Space: O(n)
Build a frequency map by iterating through the string once.
function charFrequency(str) {
const freq = {};
for (const ch of str) {
freq[ch] = (freq[ch] || 0) + 1;
}
return freq;
}
// charFrequency("banana")
// => { b: 1, a: 3, n: 2 }
// To find the most frequent character:
function mostFrequent(str) {
const freq = charFrequency(str);
return Object.entries(freq).sort((a, b) => b[1] - a[1])[0];
}
Time: O(n) | Space: O(k) where k is the number of unique characters.
Use the sliding window pattern with a Map to track the last index of each character. Shrink the left boundary when a repeat is found.
function lengthOfLongestSubstring(s) {
const map = new Map();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
if (map.has(s[right]) && map.get(s[right]) >= left) {
left = map.get(s[right]) + 1;
}
map.set(s[right], right);
best = Math.max(best, right - left + 1);
}
return best;
}
// Input: "abcabcbb" => Output: 3 (window "abc")
// Input: "bbbbb" => Output: 1 (window "b")
// Input: "pwwkew" => Output: 3 (window "wke")
Time: O(n) | Space: O(min(n, charset))
Use a stack. Push opening brackets; on a closing bracket, check the top of the stack for a match.
function isValid(s) {
const stack = [];
const pairs = { ')': '(', ']': '[', '}': '{' };
for (const ch of s) {
if ('([{'.includes(ch)) {
stack.push(ch);
} else {
if (stack.pop() !== pairs[ch]) return false;
}
}
return stack.length === 0;
}
// Input: "()" => Output: true
// Input: "()[]{}" => Output: true
// Input: "(]" => Output: false
// Input: "([)]" => Output: false
Time: O(n) | Space: O(n)
Use backtracking: fix one character at a time and recursively permute the rest. Swap characters in place to avoid extra space.
function permutations(str) {
const result = [];
function backtrack(arr, start) {
if (start === arr.length) {
result.push(arr.join(''));
return;
}
for (let i = start; i < arr.length; i++) {
[arr[start], arr[i]] = [arr[i], arr[start]]; // swap
backtrack(arr, start + 1);
[arr[start], arr[i]] = [arr[i], arr[start]]; // undo swap
}
}
backtrack(str.split(''), 0);
return result;
}
// Input: "abc" => Output: ["abc","acb","bac","bca","cab","cba"]
// Input: "ab" => Output: ["ab","ba"]
Time: O(n! × n) | Space: O(n) recursion depth
A clean O(n×m) brute force works well for interviews. For production, use KMP algorithm for O(n+m).
// Brute force
function strStr(haystack, needle) {
if (!needle) return 0;
for (let i = 0; i <= haystack.length - needle.length; i++) {
if (haystack.slice(i, i + needle.length) === needle) return i;
}
return -1;
}
// Input: haystack="hello", needle="ll" => Output: 2
// Input: haystack="aaaaa", needle="bba" => Output: -1
// Input: haystack="sadbutsad", needle="sad" => Output: 0
Brute force: O(n×m) time | KMP: O(n+m) time
Each term describes the previous one: count consecutive identical digits and write count+digit pairs.
function countAndSay(n) {
let result = "1";
for (let i = 1; i < n; i++) {
let next = '';
let j = 0;
while (j < result.length) {
const ch = result[j];
let count = 0;
while (j < result.length && result[j] === ch) { j++; count++; }
next += count + ch;
}
result = next;
}
return result;
}
// Input: n=1 => Output: "1"
// Input: n=2 => Output: "11" (one 1)
// Input: n=4 => Output: "1211" (one 1, one 2, two 1s)
Time: O(n × m) where m is avg string length | Space: O(m)
Use expand around center: for each character (and each pair), expand outward while characters match. Track the longest expansion.
function longestPalindrome(s) {
let start = 0, maxLen = 1;
function expand(l, r) {
while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }
if (r - l - 1 > maxLen) { start = l + 1; maxLen = r - l - 1; }
}
for (let i = 0; i < s.length; i++) {
expand(i, i); // odd length
expand(i, i + 1); // even length
}
return s.substring(start, start + maxLen);
}
// Input: "babad" => Output: "bab" (or "aba")
// Input: "cbbd" => Output: "bb"
// Input: "racecar" => Output: "racecar"
Time: O(n²) | Space: O(1)
Use dynamic programming. dp[i][j] is true if pattern[0..j-1] matches string[0..i-1]. Handle * (zero or more chars) and ? (any single char).
function isMatch(s, p) {
const m = s.length, n = p.length;
const dp = Array.from({length: m+1}, () => new Array(n+1).fill(false));
dp[0][0] = true;
for (let j = 1; j <= n; j++) dp[0][j] = p[j-1] === '*' && dp[0][j-1];
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (p[j-1] === '*') dp[i][j] = dp[i-1][j] || dp[i][j-1];
else dp[i][j] = (p[j-1] === '?' || p[j-1] === s[i-1]) && dp[i-1][j-1];
}
}
return dp[m][n];
}
// Input: s="aa", p="a" => Output: false
// Input: s="aa", p="*" => Output: true
// Input: s="adceb", p="*a*b" => Output: true
Time: O(m×n) | Space: O(m×n)
Sort each word to get its canonical form, then group words with the same sorted form using a Map.
function groupAnagrams(strs) {
const map = new Map();
for (const str of strs) {
const key = str.split('').sort().join('');
if (!map.has(key)) map.set(key, []);
map.get(key).push(str);
}
return [...map.values()];
}
// Input: ["eat","tea","tan","ate","nat","bat"]
// Output: [["eat","tea","ate"],["tan","nat"],["bat"]]
// Input: [""] => Output: [[""]]
// Input: ["a"] => Output: [["a"]]
Time: O(n × k × log k) where k is max word length | Space: O(n × k)
Process from right to left. If the current value is less than the value to its right, subtract it; otherwise add it.
function romanToInt(s) {
const val = { I:1, V:5, X:10, L:50, C:100, D:500, M:1000 };
let result = 0;
for (let i = 0; i < s.length; i++) {
const curr = val[s[i]], next = val[s[i + 1]];
if (next && curr < next) result -= curr;
else result += curr;
}
return result;
}
// Input: "III" => Output: 3
// Input: "IV" => Output: 4 (I before V = subtract)
// Input: "MCMXCIV" => Output: 1994
Time: O(n) | Space: O(1)
Use a sliding window with two frequency maps: required characters vs window characters. Expand right until all covered, then shrink left.
function minWindow(s, t) {
const need = {}, window = {};
for (const c of t) need[c] = (need[c] || 0) + 1;
let have = 0, required = Object.keys(need).length;
let left = 0, res = '', minLen = Infinity;
for (let right = 0; right < s.length; right++) {
const c = s[right];
window[c] = (window[c] || 0) + 1;
if (need[c] && window[c] === need[c]) have++;
while (have === required) {
if (right - left + 1 < minLen) {
minLen = right - left + 1;
res = s.slice(left, right + 1);
}
window[s[left]]--;
if (need[s[left]] && window[s[left]] < need[s[left]]) have--;
left++;
}
}
return res;
}
// Input: s="ADOBECODEBANC", t="ABC" => Output: "BANC"
// Input: s="a", t="a" => Output: "a"
Time: O(n + m) | Space: O(n + m)
Validate structure: optional sign, digits, optional decimal point with digits, optional exponent with sign and digits.
function isNumber(s) {
s = s.trim();
// Regex approach — covers all valid cases
return /^[+-]?(d+.?d*|.d+)([eE][+-]?d+)?$/.test(s);
}
// Manual flag approach:
function isNumberManual(s) {
let seenDigit = false, seenDot = false, seenE = false;
s = s.trim();
for (let i = 0; i < s.length; i++) {
const c = s[i];
if ('0' <= c && c <= '9') seenDigit = true;
else if (c === '.') { if (seenDot || seenE) return false; seenDot = true; }
else if (c === 'e' || c === 'E') { if (seenE || !seenDigit) return false; seenE = true; seenDigit = false; }
else if (c === '+' || c === '-') { if (i !== 0 && s[i-1] !== 'e' && s[i-1] !== 'E') return false; }
else return false;
}
return seenDigit;
}
// Input: "2" => Output: true
// Input: "0089" => Output: true
// Input: "e3" => Output: false
// Input: "1e" => Output: false
Time: O(n) | Space: O(1)
Use vertical scanning: compare character by character column-wise across all strings. Stop at the first mismatch.
function longestCommonPrefix(strs) {
if (!strs.length) return '';
for (let i = 0; i < strs[0].length; i++) {
const ch = strs[0][i];
for (let j = 1; j < strs.length; j++) {
if (i >= strs[j].length || strs[j][i] !== ch) {
return strs[0].slice(0, i);
}
}
}
return strs[0];
}
// Input: ["flower","flow","flight"] => Output: "fl"
// Input: ["dog","racecar","car"] => Output: ""
// Input: ["interview","internet","intercept"] => Output: "inter"
Time: O(n × m) where m is shortest string length | Space: O(1)
Split by spaces, reverse the array, then join. Handle multiple spaces and leading/trailing whitespace.
function reverseWords(s) {
return s.trim().split(/s+/).reverse().join(' ');
}
// Input: "the sky is blue" => Output: "blue is sky the"
// Input: " hello world " => Output: "world hello"
// Input: "a good example" => Output: "example good a"
// In-place without split (for interview challenge):
function reverseWordsInPlace(s) {
const arr = s.trim().split(/s+/);
let l = 0, r = arr.length - 1;
while (l < r) { [arr[l], arr[r]] = [arr[r], arr[l]]; l++; r--; }
return arr.join(' ');
}
Time: O(n) | Space: O(n)
Use a stack to save state when entering parentheses. Track current number and sign as you scan.
function calculate(s) {
const stack = [];
let num = 0, sign = 1, result = 0;
for (const ch of s) {
if (ch >= '0' && ch <= '9') {
num = num * 10 + Number(ch);
} else if (ch === '+' || ch === '-') {
result += sign * num;
num = 0;
sign = ch === '+' ? 1 : -1;
} else if (ch === '(') {
stack.push(result, sign); // save state
result = 0; sign = 1;
} else if (ch === ')') {
result += sign * num;
num = 0;
result *= stack.pop(); // apply saved sign
result += stack.pop(); // restore saved result
}
}
return result + sign * num;
}
// Input: "1 + 1" => Output: 2
// Input: " 2-1 + 2 " => Output: 3
// Input: "(1+(4+5+2)-3)+(6+8)" => Output: 23
Time: O(n) | Space: O(n)