These are the notes for JavaScript Coding Questions, episode 14, interview and placement practice for people who finished the SyntaxPilot JavaScript course. Three of the most asked string questions, each with a classic tool: the longest substring without repeating characters (a sliding window), string compression aabccc → a2b1c3 (a run counter), and valid parentheses (a stack).
Each question follows the same steps: read the problem, think out loud, the obvious attempt, a real failure, why, the fix, every test case, and the complexity.
Every program was run with Node.js 24 (node main.js), the SyntaxPilot compiler's JavaScript command, and every output below is real. Plain modern JavaScript, no packages.
About the timings. Lines like
brute: 2.286sare copied from a real run on one machine; your numbers will differ. What matters is the size of the gap.
Q1: Longest substring without repeating characters
Problem. Return the length of the longest substring (a piece of the string with no gaps) in which no character repeats.
"abcabcbb" → 3 ("abc")
"bbbbb" → 1 ("b")
"pwwkew" → 3 ("wke"; "pwke" skips a character, so it is not a substring)
"abba" → 2 ("ab" or "ba")
"dvdf" → 3 ("vdf")
"" → 0
Real life: the longest stretch of a playlist in which no song plays twice.
Think out loud
- Substring means consecutive characters. A subsequence may skip characters; that is a different question.
- Edge cases: all the same character, empty string, a repeat far back (
abba), long input.
The obvious attempt: check every substring
function longest(s) {
let best = 0;
for (let i = 0; i < s.length; i++) {
for (let j = i; j < s.length; j++) {
const part = s.slice(i, j + 1);
if (new Set(part).size === part.length) best = Math.max(best, part.length);
}
}
return best;
}
console.log(longest("abcabcbb"), longest("bbbbb"), longest("pwwkew"));
const codes = Array.from({ length: 600 }, (_, i) => 0x4e00 + i);
const big = String.fromCharCode(...codes);
console.time("brute");
console.log(longest(big));
console.timeEnd("brute");
3 1 3
600
brute: 1.936s
Correct, but seconds for 600 characters. There are about n²/2 substrings, and building a Set from each costs up to n more: O(n³) time. Double the input and it becomes about eight times slower. (String.fromCharCode(...codes) builds a string from character codes; codes from 0x4e00 are 600 different Chinese characters, so nothing repeats.)
The idea: a sliding window (a playlist with no repeats)
Keep a window s[left..right] with no repeats.
- Each step,
rightmoves forward one character (the next song joins). - If that character is already in the window,
leftjumps to one past its earlier position (drop songs up to the earlier play). - A Map
lastremembers the last position of each character, so the jump is instant.
Both ends only move forward, so the whole string is walked once.
First window, and the abba trap
function longest(s) {
const last = new Map();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
const c = s[right];
if (last.has(c)) left = last.get(c) + 1;
last.set(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}
console.log(longest("abcabcbb"), longest("bbbbb"), longest("pwwkew"));
console.log(longest("abba"));
3 1 3
3
abba should be 2. At the second b (index 2), left becomes 2. At the last a (index 3), last.get("a") is 0, which is already outside the window, but left = 0 + 1 moves left back to 1. The window bba is counted, with b twice.
Fix: left never moves back
function longest(s) {
const last = new Map();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
const c = s[right];
if (last.has(c)) left = Math.max(left, last.get(c) + 1);
last.set(c, right);
best = Math.max(best, right - left + 1);
}
return best;
}
console.log(longest("abcabcbb"), longest("bbbbb"), longest("pwwkew"));
console.log(longest("abba"), longest("dvdf"), longest(""));
const big = "abcdefghijklmnopqrstuvwxyz".repeat(40000);
console.time("window");
console.log(big.length, longest(big));
console.timeEnd("window");
3 1 3
2 3 0
1040000 26
window: 30.823ms
Complexity: O(n) time (right moves n times, left only forward); O(k) space for the Map, where k is the number of different characters.
Q2: String compression
Problem. Write each run (consecutive equal characters) as the character followed by its length.
"aabccc" → "a2b1c3"
"aabccaa" → "a2b1c2a2" (the final a's are a new run)
"a" → "a1"
"" → ""
Real life: a waiter calling out "2 roti, 1 dal, 3 chai" instead of every plate.
The obvious attempt: a counting Map
function compress(s) {
const count = new Map();
for (const c of s) count.set(c, (count.get(c) ?? 0) + 1);
let out = "";
for (const [c, n] of count) out += c + n;
return out;
}
console.log(compress("aabccc"));
console.log(compress("aabccaa"));
a2b1c3
a4b1c2
A Map counts all the as in the whole string and forgets where they were. Compression needs runs: compare each character with the one before it.
Runs, and the lost last run
function compress(s) {
let out = "", run = 1;
for (let i = 1; i < s.length; i++) {
if (s[i] === s[i - 1]) run++;
else { out += s[i - 1] + run; run = 1; }
}
return out;
}
console.log(compress("aabccc"));
console.log(compress("aabccaa"));
a2b1
a2b1c2
A run is written only when a different character arrives. The last run is never followed by one, so it is never written: an off-by-one error.
Fix: one more step, i <= s.length
s[s.length] is undefined, which is different from every character, so the extra step closes the last run. For "" the loop never runs and the answer is "".
function compress(s) {
let out = "", run = 1;
for (let i = 1; i <= s.length; i++) {
if (s[i] === s[i - 1]) run++;
else { out += s[i - 1] + run; run = 1; }
}
return out;
}
console.log(compress("aabccc"));
console.log(compress("aabccaa"));
console.log(JSON.stringify(compress("a")), JSON.stringify(compress("")));
console.log(compress("abc"));
const big = "ab".repeat(500000) + "c".repeat(1000000);
console.time("compress");
console.log(compress(big).length);
console.timeEnd("compress");
a2b1c3
a2b1c2a2
"a1" ""
a1b1c1
2000008
compress: 97.691ms
"abc" becomes "a1b1c1", longer than the input. A common follow-up: return the original when the compressed string is not shorter (practice question 2).
Complexity: one pass, O(n) time; O(n) space for the output.
Q3: Are the brackets balanced?
Problem. Every (, [ and { must be closed by the same kind, in the right order (nesting is fine). Other characters are ignored.
"()[]{}" → true
"{[()]}" → true
"((" → false (never closed)
"([)]" → false (wrong order)
")(" → false (a close with nothing open)
"" → true
"if (a[0] > 1) { log(a); }" → true
"if (a[0] > 1) { log(a; }" → false
Real life: your code editor marking a missing bracket in red.
The obvious attempt: one counter
function isValid(s) {
let open = 0;
for (const c of s) {
if ("([{".includes(c)) open++;
else open--;
}
return open === 0;
}
console.log(isValid("()[]{}"), isValid("{[()]}"));
console.log(isValid("(("), isValid("([)]"), isValid(")("));
true true
false true true
Stopping when the counter goes below zero fixes )(:
function isValid(s) {
let open = 0;
for (const c of s) {
if ("([{".includes(c)) open++;
else open--;
if (open < 0) return false;
}
return open === 0;
}
console.log(isValid("()[]{}"), isValid("{[()]}"));
console.log(isValid("(("), isValid("([)]"), isValid(")("));
true true
false true false
But ([)] is still true: a counter knows how many brackets are open, not which ones or in what order.
The idea: a stack (boxes inside boxes)
A stack is a pile where you add and remove only at the top: last in, first out (LIFO). In JavaScript an array is a stack: push adds to the end, pop removes and returns the last item (or undefined if the array is empty).
- Opening bracket:
pushit (open a box, put it on top). - Closing bracket:
popthe top; it must be the matching opener (only the top box can be closed). - At the end the stack must be empty (every box closed).
function isValid(s) {
const pair = { ")": "(", "]": "[", "}": "{" };
const stack = [];
for (const c of s) {
if ("([{".includes(c)) stack.push(c);
else if (stack.pop() !== pair[c]) return false;
}
return stack.length === 0;
}
console.log(isValid("()[]{}"), isValid("{[()]}"));
console.log(isValid("(("), isValid("([)]"), isValid(")("));
console.log(isValid(""), isValid("]"));
console.log(isValid("if (a[0] > 1) { log(a); }"));
true true
false false false
true false
false
Every bracket-only test is right, and a lone ] is false because [].pop() is undefined. But real code returns false: every non-opener goes to the else, so the letter i pops the stack.
Fix: only closing brackets pop
function isValid(s) {
const pair = { ")": "(", "]": "[", "}": "{" };
const stack = [];
for (const c of s) {
if ("([{".includes(c)) stack.push(c);
else if (c in pair && stack.pop() !== pair[c]) return false;
}
return stack.length === 0;
}
console.log(isValid("()[]{}"), isValid("{[()]}"));
console.log(isValid("(("), isValid("([)]"), isValid(")("));
console.log(isValid(""), isValid("]"));
console.log(isValid("if (a[0] > 1) { log(a); }"));
console.log(isValid("if (a[0] > 1) { log(a; }"));
true true
false false false
true false
true
false
c in pair is true only for ), ] and }. Thanks to &&, pop runs only for them (short-circuit evaluation).
Complexity: O(n) time; O(n) space in the worst case (all openers).
Complexity summary
| Question | Approach | Time | Extra space |
|---|---|---|---|
| Longest substring | every substring + Set | O(n³) | O(n) |
| Longest substring | sliding window + Map of last positions | O(n) | O(k) |
| Compression | counting Map | O(n), and wrong | O(k) |
| Compression | run counter, i <= s.length |
O(n) | O(n) output |
| Brackets | one counter | O(n), and wrong | O(1) |
| Brackets | stack | O(n) | O(n) |
Common mistakes (and the exact outputs)
| Mistake | Code | What you see | Why | Fix |
|---|---|---|---|---|
| Checking every substring | two loops + new Set(part) |
brute: 1.936s for 600 characters |
O(n³) | sliding window |
left moving back |
left = last.get(c) + 1 |
3 for "abba" |
the old position may be outside the window | Math.max(left, last.get(c) + 1) |
| Substring vs subsequence | counting pwke |
4 instead of 3 |
a substring has no gaps | only consecutive characters |
| Counting instead of runs | a counting Map | a4b1c2 for "aabccaa" |
counts lose position | compare with s[i - 1] |
| Off-by-one | i < s.length |
a2b1 for "aabccc" |
the last run is never closed | i <= s.length |
| Compressing longer | always return out |
a1b1c1 for "abc" |
single runs double the length | compare lengths |
| One counter for brackets | open++ / open-- |
true for "([)]" and ")(" |
it forgets which bracket, and order | a stack |
| Popping on every character | else if (stack.pop() !== ...) |
false for real code |
letters pop the stack | c in pair && ... |
| Forgetting the final check | return true |
true for "((" |
openers left on the stack | stack.length === 0 |
Mini project: attendance by SMS
A school sends each month's attendance (P present, A absent, L leave) to parents by SMS, where every character counts. Compress it, check that it decodes back to exactly the same string, and report the longest present streak.
// Mini project: send a month's attendance in a short SMS, and read it back
function compress(s) {
let out = "", run = 1;
for (let i = 1; i <= s.length; i++) {
if (s[i] === s[i - 1]) run++;
else { out += s[i - 1] + run; run = 1; }
}
return out;
}
const decompress = s => s.replace(/(\D)(\d+)/g, (m, c, n) => c.repeat(Number(n)));
function longestStreak(s, mark) {
let best = 0, run = 0;
for (const c of s) { run = c === mark ? run + 1 : 0; best = Math.max(best, run); }
return best;
}
const month = "PPPPPPAPPPPPPPPPPPLLPPPPPPPPPP";
const sms = compress(month);
console.log(sms, sms.length, "vs", month.length);
console.log(decompress(sms) === month);
console.log("longest present streak:", longestStreak(month, "P"));
P6A1P11L2P10 12 vs 30
true
longest present streak: 11
This is run-length encoding, used for real in fax machines, simple image formats and in game level data.
Your turn: decompress (solution)
decompress("a2b1c3") → "aabccc", and a count can have several digits: decompress("x12") is twelve xs.
Solution
(\D) is one character that is not a digit (group 1), (\d+) is one or more digits (group 2). The callback repeats the character; Number(n) turns the digits into a number.
const decompress = s => s.replace(/(\D)(\d+)/g, (m, c, n) => c.repeat(Number(n)));
console.log(decompress("a2b1c3"));
console.log(decompress("x12"));
console.log(JSON.stringify(decompress("")));
aabccc
xxxxxxxxxxxx
""
O(m) time and space, where m is the length of the output.
Practice questions (with solutions)
1. Compress only if shorter.
Solution
function compressIfShorter(s) {
let out = "", run = 1;
for (let i = 1; i <= s.length; i++) {
if (s[i] === s[i - 1]) run++;
else { out += s[i - 1] + run; run = 1; }
}
return out.length < s.length ? out : s;
}
console.log(compressIfShorter("aaabbbbcc"), compressIfShorter("abc"), compressIfShorter("aab"));
a3b4c2 abc aab
2. Longest substring with at most 2 different characters.
Solution
A sliding window with a counting Map: grow on the right; while the window has more than 2 different characters, shrink from the left (decrease the count, delete it at 0).
function longestTwo(s) {
const count = new Map();
let left = 0, best = 0;
for (let right = 0; right < s.length; right++) {
count.set(s[right], (count.get(s[right]) ?? 0) + 1);
while (count.size > 2) {
const c = s[left++];
count.set(c, count.get(c) - 1);
if (count.get(c) === 0) count.delete(c);
}
best = Math.max(best, right - left + 1);
}
return best;
}
console.log(longestTwo("eceba"), longestTwo("ccaabbb"), longestTwo(""), longestTwo("aaaa"));
3 5 0 4
O(n) time: each character enters and leaves the window at most once.
3. Minimum brackets to add to make ( / ) valid.
Solution
With one kind of bracket a counter is enough. A ) with nothing open needs an added (; openers left at the end each need a ).
function minAdd(s) {
let open = 0, add = 0;
for (const c of s) {
if (c === "(") open++;
else if (open > 0) open--;
else add++;
}
return add + open;
}
console.log(minAdd("())"), minAdd("((("), minAdd("()"), minAdd(")))((("));
1 3 0 6
Quick quiz
1. (From the video.) What does this print?
const stack = [];
console.log(stack.pop(), stack.length);
(A) TypeError (B) undefined 0 (C) null 0 (D) undefined -1
Answer
(B) undefined 0. pop on an empty array does not throw; it returns undefined and the length stays 0.
2. What does this print?
const s = "abc";
console.log(s[3], s[3] === s[2]);
console.log("x".repeat(3), "ab".repeat(0) === "");
Answer
undefined false
xxx true
Reading past the end of a string gives undefined, which is why i <= s.length closes the last run.
3. In the sliding window, why is left = Math.max(left, last.get(c) + 1) and not left = last.get(c) + 1?
Answer
last remembers positions from before the window started. If the earlier copy is already outside the window, last.get(c) + 1 is smaller than left and would move the window back over characters that repeat (abba → 3).
Interview questions
- Longest substring without repeating characters in O(n)? Sliding window with a Map of last positions;
left = Math.max(left, last + 1). - What is a sliding window? A range
[left, right]over an array or string that grows on the right and shrinks on the left, so each element is processed a constant number of times. - Substring vs subsequence? A substring is consecutive; a subsequence may skip characters (keeping order).
- What is run-length encoding? Writing each run of equal values as the value and its count:
aabccc → a2b1c3. - Why does a simple run loop lose the last run? It writes a run only when the character changes; the last run never sees a change.
- Check balanced brackets. A stack: push openers, pop on closers and compare, empty at the end. O(n).
- Why isn't a counter enough? It ignores the type and order of brackets (
([)]). - What is LIFO? Last in, first out: the stack's rule.
- What does
[].pop()return?undefined. - What if there is only one kind of bracket? A counter that never goes below zero and ends at zero is enough.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Substring | Consecutive characters of a string | "wke" in "pwwkew" |
| Subsequence | Characters in order, gaps allowed | "pwke" in "pwwkew" |
| Brute force | Try every possibility | every substring |
| O(n³) | Time grows with the cube of the input | 2× input → ~8× time |
Set |
A collection of unique values | new Set("aab").size → 2 |
| Sliding window | A [left, right] range that moves forward |
s.slice(left, right + 1) |
left / right pointers |
Indexes of the window's ends | right - left + 1 = length |
| Map of last positions | Character → its latest index | last.set(c, right) |
Math.max |
The larger of its arguments | Math.max(2, 1) → 2 |
String.fromCharCode |
Characters for codes | String.fromCharCode(65) → "A" |
repeat(n) |
A string repeated n times |
"ab".repeat(2) → "abab" |
| Run | Consecutive equal characters | ccc in aabccc |
| Run-length encoding | Each run as character + count | a2b1c3 |
| Off-by-one error | A loop that does one step too few or too many | i < s.length loses the last run |
s[s.length] |
Past the end: undefined |
"abc"[3] |
| Stack | Add and remove only at the top | an array with push/pop |
| LIFO | Last in, first out | the last box opened closes first |
push / pop |
Add to / remove from the end of an array | [1].pop() → 1 |
in operator |
Does the object have this key? | ")" in pair → true |
Short-circuit && |
The right side runs only if the left is truthy | c in pair && stack.pop() |
\D / \d+ |
A non-digit / one or more digits | /(\D)(\d+)/g |
Number(s) |
Turn text into a number | Number("12") → 12 |
console.time / timeEnd |
Measure the time between two points | brute: 1.936s |
Summary
- Longest substring without repeats: checking every substring is O(n³). A sliding window with a Map of last positions is O(n), and
leftmust never move back (Math.max), orabbagives 3. - Compression: a counting Map loses positions; count runs by comparing with the previous character, and close the last run (
i <= s.length). Return the original if the result isn't shorter, when asked. - Brackets: a counter forgets which bracket is open. A stack (push openers, pop and compare on closers, empty at the end) is O(n); only closing brackets should pop.
Next episode: Object questions I: deep clone (the JSON trap with Date and undefined, recursion, structuredClone), deep equality of two objects, and counting keys.