DSA for Interviews, From Zero

Part 7 · Lesson 30 · read

String Patterns

Palindromes, reversing words, common prefixes, Roman numerals and compression.

On this page

  1. Strings are arrays of characters
  2. Palindromes with two pointers
  3. Longest palindromic substring: expand around the centre
  4. Traced: expanding around every centre
  5. Longest common prefix
  6. Roman numerals: look one character ahead
  7. String compression: read pointer, write pointer
  8. Rotation check: the doubled-string trick
  9. Practice questions (7)
  10. Make it stick
  11. What's next

Strings are arrays of characters

Part 7 uses what you already know (two pointers, windows and frequency maps) on text. The only new idea is how JavaScript treats a string, so we start there. A string is a piece of text, a sequence of characters such as “hello”.

A string behaves like a read-only array. s[i] gives the character at index i (its position, counting from 0). s.length is the number of characters. A for loop can walk through it. But a string is immutable, which means you can never change a character inside it. Every “change” builds a new string and leaves the old one as it was.

JavaScript
const s = "hello";console.log(s[0]);            // hconsole.log(s[s.length - 1]); // oconsole.log(s.slice(1, 4));   // ell   (index 1 up to, not including, 4)s[0] = "J";                   // ignored (in strict mode this throws an error): strings cannot be changedconsole.log(s);               // helloconst chars = [...s];         // turn the string into an array of characterschars[0] = "J";console.log(chars.join(""));  // Jello
The hidden cost of building strings
result += ch inside a loop creates a new string each time. In some languages this makes a loop that looks like O(n) behave more like O(n²), because every step copies the whole string. JavaScript engines are usually fast enough here. But for interviews, the safe habit is to collect the pieces in an array and call join("") once at the end. (join glues the array items into one string.)

These methods are worth knowing well. slice(a, b) copies the part from index a up to (not including) b. startsWith checks the beginning of a string. includes checks whether some text is inside. indexOf gives the position of some text, or −1. split("") turns a string into an array of characters. charCodeAt gives the number code of a character. toLowerCase makes all letters small. And [...s].reverse().join("") reverses a string.

Palindromes with two pointers

A palindrome is a word or text that reads the same forwards and backwards, such as “racecar” or “noon”. Put one pointer (an index that marks a position) at each end and walk them towards each other. If every pair of characters matches, the text is a palindrome. This is the two-pointer technique from Lesson 21, used on text. It takes O(n) time and O(1) extra space.

JavaScript
function isPalindrome(s) {  let l = 0, r = s.length - 1;  while (l < r) {    if (s[l] !== s[r]) return false;   // mismatch, so it is not a palindrome    l++;    r--;  }  return true;                          // every pair matched}console.log(isPalindrome("racecar")); // trueconsole.log(isPalindrome("abca"));    // falseconsole.log(isPalindrome(""));        // true

Real questions add extra characters: spaces, punctuation and capital letters. Do not build a cleaned copy unless you must. Instead, let each pointer skip the characters that do not count.

JavaScript
// Skip anything that is not a letter or digit, and ignore upper/lower case.function isCleanPalindrome(s) {  const isAlnum = (c) => /[a-z0-9]/i.test(c);  let l = 0, r = s.length - 1;  while (l < r) {    while (l < r && !isAlnum(s[l])) l++;    while (l < r && !isAlnum(s[r])) r--;    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;    l++;    r--;  }  return true;}console.log(isCleanPalindrome("A man, a plan, a canal: Panama")); // trueconsole.log(isCleanPalindrome("race a car"));                     // false

Longest palindromic substring: expand around the centre

A substring is a continuous part of a string. Finding the longest palindrome inside a string looks hard, but every palindrome has a centre. An odd-length palindrome (“aba”) is centred on one character. An even-length palindrome (“abba”) is centred between two characters. So try every possible centre and expand outwards while the two ends match.

  • There are 2n − 1 centres (n characters plus n − 1 gaps between them).
  • Each expansion costs up to O(n) time, so the total is O(n²) time and O(1) extra space.
  • Checking every substring and testing each one would take O(n³) time. Expanding is much better.
JavaScript
function longestPalindrome(s) {  let start = 0, best = 0;  // Grow outwards from the centre while both ends match; return the palindrome's length.  function expand(l, r) {    while (l >= 0 && r < s.length && s[l] === s[r]) {      l--;      r++;    }    return r - l - 1;  }  for (let i = 0; i < s.length; i++) {    const len = Math.max(expand(i, i), expand(i, i + 1)); // odd centre, even centre    if (len > best) {      best = len;      start = i - Math.floor((len - 1) / 2);    }  }  return s.slice(start, start + best);}console.log(longestPalindrome("babad")); // babconsole.log(longestPalindrome("cbbd"));  // bb

expand returns r - l - 1. When the loop stops, l and r have both stepped one place past the palindrome, so we remove those two extra places. For the odd case, expand(i, i) starts with a palindrome of length 1. For the even case, expand(i, i + 1) may fail at once and return 0.

Traced: expanding around every centre

step 1 / 12
Set up
start = 0, best = 0

No palindrome found yet. Every single character is a palindrome of length 1, so best will become at least 1.

1const s = "babad";▶let start = 0, best = 0;3for (let i = 0; i < s.length; i++) {4  const len = Math.max(expand(i, i), expand(i, i + 1));5  if (len > best) {6    best = len;7    start = i - Math.floor((len - 1) / 2);8  }9}10console.log(s.slice(start, start + best));
Variables
s"babad"
start0
best0
Console
(nothing printed yet)
Each centre is expanded in both the odd form and the even form. We remember the longest result so far. · interactive
Dry run · longest palindrome in "babad"
Centre iCharoddevenbest so far
0b101 (b)
1a303 (bab)
2b303 (bab)
3a103 (bab)
4d103 (bab)

Centre 1 expands from “a” to “bab”. Centre 2 finds “aba”, which has the same length, so we keep the first one.

Longest common prefix

A prefix is the beginning part of a string. The common prefix of a list of words is the longest beginning that all the words share. It can never be longer than the first word. Start with prefix = strs[0]. Compare it with each next word, and cut characters off the end of the prefix until the word starts with it. When the prefix becomes empty, every word “starts with” it, so the loop always ends.

JavaScript
function longestCommonPrefix(strs) {  let prefix = strs[0];  for (let i = 1; i < strs.length; i++) {    // make the prefix shorter until the next word starts with it    while (!strs[i].startsWith(prefix)) {      prefix = prefix.slice(0, -1);    }  }  return prefix;}console.log(longestCommonPrefix(["flower", "flow", "flight"])); // flconsole.log(longestCommonPrefix(["dog", "racecar", "car"]));    // (empty)

The cost is O(total characters) in the worst case. Another way is to scan column by column: compare character 0 of every word, then character 1, and stop at the first mismatch. Practice question 3 shows both ways.

Roman numerals: look one character ahead

Roman numerals are letters that stand for numbers: I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000. You add the values from left to right, with one exception. When a small value sits before a larger one (IV, IX, XL, XC, CD, CM), the small value is subtracted. So walk through the string. If the current value is smaller than the next value, subtract it. Otherwise, add it.

JavaScript
function romanToInt(s) {  const value = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };  let total = 0;  for (let i = 0; i < s.length; i++) {    const smallerThanNext = i + 1 < s.length && value[s[i]] < value[s[i + 1]];    if (smallerThanNext) total -= value[s[i]];   // IV: the I counts as −1    else total += value[s[i]];  }  return total;}console.log(romanToInt("III"));     // 3console.log(romanToInt("LVIII"));   // 58console.log(romanToInt("MCMXCIV")); // 1994
Dry run · MCMXCIV = 1994
CharValueNext bigger?Total after
M1000no1000
C100yes (M)900
M1000no1900
X10yes (C)1890
C100no (I is smaller)1990
I1yes (V)1989
V5no (end)1994

String compression: read pointer, write pointer

A run is a group of the same character in a row. Compress each run into the character plus its count: aabbccc becomes a2b2c3. A single character stays as it is. To do this in place (inside the same array, without making a second one), use two pointers that both move forward. A read pointer finds each run. A write pointer records the result. The write pointer can never overtake the read pointer, because the compressed form is never longer than the run it replaces.

JavaScript
function compress(chars) {  let write = 0;   // where the next compressed character goes  let i = 0;       // start of the current run  while (i < chars.length) {    const ch = chars[i];    let j = i;    while (j < chars.length && chars[j] === ch) j++;   // j stops after the run    chars[write++] = ch;    if (j - i > 1) {      for (const digit of String(j - i)) chars[write++] = digit;    }    i = j;  }  return write;    // the new length; chars[0..write) holds the answer}const chars = ["a", "a", "b", "b", "c", "c", "c"];const n = compress(chars);console.log(n);                         // 6console.log(chars.slice(0, n).join("")); // a2b2c3
Counts of 10 or more
A run of 12 letters becomes the letter followed by the two characters “1” and “2”. That is why the count is written with for (const digit of String(j - i)): one array slot for each digit.

Rotation check: the doubled-string trick

A rotation of a string moves some characters from the front to the back. Is “cdeab” a rotation of “abcde”? Join the original to itself: “abcdeabcde”. Every rotation of the original appears inside this doubled string as a substring. So the check has two parts: the lengths are the same, and the doubled string includes the other string.

JavaScript
function isRotation(a, b) {  return a.length === b.length && (a + a).includes(b);}console.log(isRotation("abcde", "cdeab")); // trueconsole.log(isRotation("abcde", "abced")); // false

Practice questions

Before you write the loop, say the pointer moves out loud. Where does each pointer start, and when does it move?

Q1Valid palindromeEasy

Return true if the string is a palindrome after you change it to lower case and remove every character that is not a letter or digit.

Example 1
Input: "A man, a plan, a canal: Panama"
Output: true
Explanation: Keeping only letters and digits and ignoring case gives "amanaplanacanalpanama", which reads the same both ways.
Example 2
Input: "race a car"
Output: false
Explanation: It becomes "raceacar". The outer pairs r/r, a/a and c/c match, but then "e" meets "a" and the check fails.
Example 3
Input: " "
Output: true
Explanation: After removing everything that is not a letter or digit, the string is empty. An empty string is a palindrome.
Stuck? Open one hint at a time
Hint 1
Put one pointer at each end. When must a pointer skip a character?
Hint 2
Skip with a nested while loop that also checks l < r. Then the pointers never cross while skipping.
Show all 2 solutions with explanations
Approach 1Clean, then compare with the reverse
The idea
  1. Lower-case the string and keep only letters and digits.
  2. Reverse that cleaned string.
  3. It is a palindrome if the two are equal.
JavaScript
function isPalindrome(s) {  const clean = s.toLowerCase().replace(/[^a-z0-9]/g, "");  return clean === [...clean].reverse().join("");}console.log(isPalindrome("A man, a plan, a canal: Panama")); // trueconsole.log(isPalindrome("race a car"));                     // falseconsole.log(isPalindrome(" "));                              // true
How it works

This is easy to read, but it builds two extra strings. It takes O(n) time and O(n) extra space.

Approach 2Two pointers that skip
The idea
  1. Start l at the front and r at the back.
  2. Move l right past characters that are not letters or digits. Move r left past them.
  3. Compare the two characters in lower case. A mismatch means the answer is false.
  4. Step both inwards and repeat while l < r.
JavaScript
function isPalindrome(s) {  const isAlnum = (c) => /[a-z0-9]/i.test(c);  let l = 0, r = s.length - 1;  while (l < r) {    while (l < r && !isAlnum(s[l])) l++;    while (l < r && !isAlnum(s[r])) r--;    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;    l++;    r--;  }  return true;}console.log(isPalindrome("A man, a plan, a canal: Panama")); // trueconsole.log(isPalindrome("race a car"));                     // falseconsole.log(isPalindrome(" "));                              // true
How it works

Every character is visited at most once, so it takes O(n) time and O(1) extra space. For " ", the inner loop moves l until it meets r. Then the outer loop ends and the answer is true.

Which approach should you use?

Use the two-pointer version in an interview. The interviewer will often ask a follow-up about extra space. (LeetCode 125.)

Q2Valid palindrome II (delete at most one character)Easy

Return true if the string can become a palindrome after deleting at most one character.

Example 1
Input: "aba"
Output: true
Explanation: Already a palindrome.
Example 2
Input: "abca"
Output: true
Explanation: Delete "b" to get "aca", or delete "c" to get "aba".
Example 3
Input: "abc"
Output: false
Explanation: Deleting any one character leaves two different letters.
Stuck? Open one hint at a time
Hint 1
Run the normal two-pointer check. What should you do at the first mismatch?
Hint 2
At the first mismatch there are only two choices: skip the left character or skip the right character. Check whether either remaining middle part is a palindrome.
Show all 2 solutions with explanations
Approach 1Try deleting each character
The idea

For every index, remove that character. Then test whether the rest is a palindrome.

JavaScript
function validPalindrome(s) {  const isPal = (t) => t === [...t].reverse().join("");  if (isPal(s)) return true;  for (let i = 0; i < s.length; i++) {    if (isPal(s.slice(0, i) + s.slice(i + 1))) return true;  }  return false;}console.log(validPalindrome("abca")); // trueconsole.log(validPalindrome("abc"));  // false
How it works

There are n deletions, and each check costs O(n), so the total is O(n²) time. It is correct, but too slow for large inputs.

Approach 2Two pointers, one allowed mismatch
The idea
  1. Move the pointers inwards while the characters match.
  2. At the first mismatch, the only way to succeed is to delete s[l] or s[r].
  3. Check the two remaining ranges, l+1 … r and l … r-1, with a plain palindrome helper function.
JavaScript
function validPalindrome(s) {  const isPal = (l, r) => {    while (l < r) {      if (s[l] !== s[r]) return false;      l++;      r--;    }    return true;  };  let l = 0, r = s.length - 1;  while (l < r) {    if (s[l] !== s[r]) return isPal(l + 1, r) || isPal(l, r - 1);    l++;    r--;  }  return true;}console.log(validPalindrome("aba"));  // trueconsole.log(validPalindrome("abca")); // trueconsole.log(validPalindrome("abc"));  // false
How it works

In “abca” the first mismatch is b vs c at l = 1, r = 2. Deleting b leaves s[2..2] = “c”, which is a palindrome, so the answer is true. The helper runs at most twice over the middle part, so the total is O(n) time and O(1) extra space.

Which approach should you use?

The key idea of this question is to branch into two choices only at the first mismatch. (LeetCode 680.)

Q3Longest common prefixEasy

Return the longest string that is a prefix of every string in the array. Return "" (an empty string) if there is none.

Example 1
Input: ["flower", "flow", "flight"]
Output: "fl"
Explanation: All three start with "fl", but "flo" fails on "flight".
Example 2
Input: ["dog", "racecar", "car"]
Output: ""
Explanation: The first letters differ, so there is no common prefix.
Stuck? Open one hint at a time
Hint 1
The answer is never longer than the shortest word.
Hint 2
Compare column by column. Is the character at index 0 the same in every word? Then is the character at index 1 the same?
Show all 2 solutions with explanations
Approach 1Shrink the prefix word by word
The idea
  1. Start with the first word as the prefix.
  2. For each next word, cut the last character off the prefix until the word starts with the prefix.
JavaScript
function longestCommonPrefix(strs) {  let prefix = strs[0];  for (let i = 1; i < strs.length; i++) {    while (!strs[i].startsWith(prefix)) prefix = prefix.slice(0, -1);  }  return prefix;}console.log(longestCommonPrefix(["flower", "flow", "flight"])); // flconsole.log(longestCommonPrefix(["dog", "racecar", "car"]));    // (empty)
How it works

O(S) time, where S is the total number of characters, and O(1) extra space.

Approach 2Column by column
The idea
  1. For each index i of the first word, take its character.
  2. If any other word is too short, or has a different character at i, return the part that has matched so far.
JavaScript
function longestCommonPrefix(strs) {  for (let i = 0; i < strs[0].length; i++) {    for (let k = 1; k < strs.length; k++) {      if (i === strs[k].length || strs[k][i] !== strs[0][i]) {        return strs[0].slice(0, i);      }    }  }  return strs[0];}console.log(longestCommonPrefix(["flower", "flow", "flight"])); // flconsole.log(longestCommonPrefix(["dog", "racecar", "car"]));    // (empty)console.log(longestCommonPrefix(["same"]));                      // same
How it works

It stops at the first column that does not match, so it never reads characters past the answer. It takes O(S) time in the worst case.

Which approach should you use?

Both are fine. Column by column is easier to explain on a whiteboard. (LeetCode 14.)

Q4Roman to integerEasy

Convert a valid Roman numeral (from 1 to 3999) to an integer (a whole number).

Example 1
Input: "III"
Output: 3
Explanation: 1 + 1 + 1.
Example 2
Input: "LVIII"
Output: 58
Explanation: L = 50, V = 5, III = 3.
Example 3
Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90, IV = 4.
Stuck? Open one hint at a time
Hint 1
Store the values of the seven symbols in an object.
Hint 2
When is a symbol subtracted instead of added? Compare it with the symbol after it.
Show all 2 solutions with explanations
Approach 1Compare with the next symbol
The idea
  1. Look up each symbol's value.
  2. If it is smaller than the next symbol's value, subtract it; otherwise add it.
JavaScript
function romanToInt(s) {  const v = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };  let total = 0;  for (let i = 0; i < s.length; i++) {    if (i + 1 < s.length && v[s[i]] < v[s[i + 1]]) total -= v[s[i]];    else total += v[s[i]];  }  return total;}console.log(romanToInt("III"));     // 3console.log(romanToInt("LVIII"));   // 58console.log(romanToInt("MCMXCIV")); // 1994
How it works

One pass: O(n) time and O(1) extra space.

Approach 2Right to left
The idea
  1. Walk from the last symbol to the first. Remember the previous value, which is the one to the right.
  2. If the current value is smaller than the value to its right, subtract it. Otherwise, add it.
JavaScript
function romanToInt(s) {  const v = { I: 1, V: 5, X: 10, L: 50, C: 100, D: 500, M: 1000 };  let total = 0, prev = 0;  for (let i = s.length - 1; i >= 0; i--) {    const cur = v[s[i]];    total += cur < prev ? -cur : cur;    prev = cur;  }  return total;}console.log(romanToInt("MCMXCIV")); // 1994console.log(romanToInt("IX"));      // 9
How it works

The cost is the same. There is no bounds check for “is there a next symbol?”, because the previous value starts at 0.

Which approach should you use?

Pick the one you can write without mistakes. (LeetCode 13.)

Q5Longest palindromic substringMedium

Return the longest substring of s that is a palindrome.

Example 1
Input: "babad"
Output: "bab"
Explanation: "aba" is also valid; either is accepted.
Example 2
Input: "cbbd"
Output: "bb"
Explanation: An even-length palindrome centred between the two b's.
Stuck? Open one hint at a time
Hint 1
Every palindrome has a centre. How many centres does a string of length n have?
Hint 2
From a centre, move one pointer left and one right while the characters match.
Hint 3
Remember the even case: the centre is between two characters.
Show all 2 solutions with explanations
Approach 1Check every substring
The idea

Make every substring, test each one with the two-pointer palindrome check, and keep the longest.

JavaScript
function longestPalindrome(s) {  const isPal = (l, r) => {    while (l < r) if (s[l++] !== s[r--]) return false;    return true;  };  let best = "";  for (let i = 0; i < s.length; i++) {    for (let j = i; j < s.length; j++) {      if (j - i + 1 > best.length && isPal(i, j)) best = s.slice(i, j + 1);    }  }  return best;}console.log(longestPalindrome("babad")); // babconsole.log(longestPalindrome("cbbd"));  // bb
How it works

There are O(n²) substrings, and each check costs O(n), so the total is O(n³) time. It is fine as a starting point, but too slow when n is 1000 or more.

Approach 2Expand around the centre
The idea
  1. For each index, expand twice: once for an odd-length palindrome and once for an even-length palindrome.
  2. Keep track of the best length and where it starts.
JavaScript
function longestPalindrome(s) {  let start = 0, best = 0;  const expand = (l, r) => {    while (l >= 0 && r < s.length && s[l] === s[r]) { l--; r++; }    return r - l - 1;  };  for (let i = 0; i < s.length; i++) {    const len = Math.max(expand(i, i), expand(i, i + 1));    if (len > best) {      best = len;      start = i - Math.floor((len - 1) / 2);    }  }  return s.slice(start, start + best);}console.log(longestPalindrome("babad")); // babconsole.log(longestPalindrome("cbbd"));  // bbconsole.log(longestPalindrome("a"));     // a
How it works

O(n²) time, O(1) extra space. Why is start = i - Math.floor((len - 1) / 2)? An odd palindrome of length 3 centred on i begins one place to the left (i − 1). An even palindrome of length 4 centred between i and i + 1 also begins at i − 1. The formula works for both.

Which approach should you use?

Expanding around the centre is the standard interview answer. (A special O(n) algorithm called Manacher's algorithm exists, but interviewers almost never expect it.) LeetCode 5.

Q6String compression (in place)Medium

Compress the character array in place. Each run of repeated characters becomes the character, followed by the length of the run if that length is more than 1. Return the new length.

Example 1
Input: ["a","a","b","b","c","c","c"]
Output: 6, chars = ["a","2","b","2","c","3"]
Explanation: The runs aa, bb and ccc become a2, b2 and c3.
Example 2
Input: ["a"]
Output: 1, chars = ["a"]
Explanation: A run of length 1 is written without a count.
Example 3
Input: ["a","b","b","b","b","b","b","b","b","b","b","b","b"]
Output: 4, chars = ["a","b","1","2"]
Explanation: There are twelve b's. The count 12 is written as two characters.
Stuck? Open one hint at a time
Hint 1
Use a read pointer to find the end of each run. Use a write pointer to record the results.
Hint 2
Write the character first. Write the count only if the run is longer than 1.
Hint 3
The count may have several digits. Write them one at a time.
Show all 2 solutions with explanations
Approach 1Build a new array
The idea

Collect the pieces in a new array. Then copy them back into chars.

JavaScript
function compress(chars) {  const out = [];  let i = 0;  while (i < chars.length) {    let j = i;    while (j < chars.length && chars[j] === chars[i]) j++;    out.push(chars[i]);    if (j - i > 1) out.push(...String(j - i));    i = j;  }  for (let k = 0; k < out.length; k++) chars[k] = out[k];  return out.length;}const a = ["a", "a", "b", "b", "c", "c", "c"];console.log(compress(a));  // 6
How it works

O(n) time, but O(n) extra space. So it breaks the “in place” rule.

Approach 2Read and write pointers
The idea
  1. i marks the start of a run. j scans to the end of the run.
  2. Write chars[i] at position write. If the run is longer than 1, write each digit of its length.
  3. Move i to j and repeat.
JavaScript
function compress(chars) {  let write = 0, i = 0;  while (i < chars.length) {    const ch = chars[i];    let j = i;    while (j < chars.length && chars[j] === ch) j++;    chars[write++] = ch;    if (j - i > 1) {      for (const d of String(j - i)) chars[write++] = d;    }    i = j;  }  return write;}const a = ["a", "a", "b", "b", "c", "c", "c"];const n = compress(a);console.log(n);                    // 6console.log(a.slice(0, n).join("")); // a2b2c3const b = ["a", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b"];const m = compress(b);console.log(m);                    // 4console.log(b.slice(0, m).join("")); // ab12
How it works

The write pointer never passes the read pointer. A run of length 2 or more is replaced by at most the same number of characters (the letter plus its digits). A run of length 1 is replaced by exactly 1 character. This takes O(n) time and O(1) extra space.

Which approach should you use?

Use the two-pointer version, because the question says “in place”. (LeetCode 443.)

Q7Rotate stringEasy

Return true if you can get goal from s by moving some characters from the front to the end, any number of times.

Example 1
Input: s = "abcde", goal = "cdeab"
Output: true
Explanation: Moving "ab" from the front of "abcde" to the back gives "cdeab".
Example 2
Input: s = "abcde", goal = "abced"
Output: false
Explanation: The letters are the same, but no rotation gives this order.
Stuck? Open one hint at a time
Hint 1
If the lengths are different, the answer is false at once.
Hint 2
Write s twice in a row. Where does every rotation of s appear in it?
Show all 2 solutions with explanations
Approach 1Try every rotation
The idea

Rotate by 1, 2, … n − 1 positions. Compare each result with the goal.

JavaScript
function rotateString(s, goal) {  if (s.length !== goal.length) return false;  for (let k = 0; k < s.length; k++) {    if (s.slice(k) + s.slice(0, k) === goal) return true;  }  return false;}console.log(rotateString("abcde", "cdeab")); // trueconsole.log(rotateString("abcde", "abced")); // false
How it works

There are n rotations, and each comparison costs O(n), so the total is O(n²) time.

Approach 2Search in the doubled string
The idea

Every rotation of s is a substring of s + s. And any substring of s + s that has the same length as s is a rotation.

JavaScript
function rotateString(s, goal) {  return s.length === goal.length && (s + s).includes(goal);}console.log(rotateString("abcde", "cdeab")); // trueconsole.log(rotateString("abcde", "abced")); // falseconsole.log(rotateString("a", "b"));         // false
How it works

The built-in includes is fast in practice. The length check prevents wrong answers such as goal = “bcdeab” (this is inside “abcdeabcde”, but it is longer than s).

Which approach should you use?

The doubled string gives a one-line answer and shows that you know the trick. (LeetCode 796.)

Dry run · Which technique for which wording?
If the question says…Reach for…Cost
is it a palindrome / ignore punctuationtwo pointers from both ends, skippingO(n), O(1)
longest palindromic substringexpand around each centreO(n²), O(1)
common prefix of many wordsshrink prefix, or scan columnsO(total chars)
convert symbols with special pairslook at the next characterO(n)
modify in place, shorter resultread pointer + write pointerO(n), O(1)
is B a rotation of Asearch B inside A + AO(n) typical

Make it stick

Make it stick — close this page, then
  1. Write the two-pointer palindrome check from memory, then extend it to skip punctuation.
  2. Explain why there are 2n − 1 centres and why the expand function returns r - l - 1.
  3. State the rule for Roman numerals and trace “MCMXCIV” on paper.
  4. Explain why the write pointer in string compression can never pass the read pointer.
  5. Prove why “a + a includes b” detects a rotation.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

What's next

You can now solve the classic text questions with pointers and centres. Lesson 31 moves from checking a whole string to using windows inside a string. It covers the longest substring without repeats, character replacement, anagrams and the well-known minimum window problem.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Related series