🚀 Supercharge Your Career — Explore Preparation tools like Free AI Mock Interviews, Job Tracker, Resume & Cover Letter Builder, and much more!
Data Structure and Algorithm
Data Structure
String
String

Strings in JavaScript

1. Introduction to String

JavaScript strings are used for storing and manipulating text. They can contain zero or more characters within quotes.

Syntax:

let string_name = "text";

Example:

let x = "Welcome to GeeksforGeeks!";
console.log(x);

Strings in JavaScript

  • Quotes: You can use single or double quotes to write strings. Quotes can be used inside a string, as long as they don't match the quotes surrounding the string.
  • Escape Characters: To use the same type of quotes within a string, or to insert special characters, use the backslash \ escape character.
  • String Length: The length of a string can be found using the built-in .length property.
  • String Breaking: For ease of understanding, long strings can be broken across lines using the \ symbol.
  • Strings as Objects: Normally, strings are primitive values, but they can also be defined as objects using the keyword new String().
let length = "GeeksforGeeks".length; // returns 13
let objStr = new String("Geeks"); // creates a string object

2. Common String Interview Problems

Problem 1: Palindrome Check

A palindrome is a word, phrase, number, or other sequences of characters which reads the same forward and backward (ignoring spaces, punctuation, and capitalization).

Method 1: Using Two Pointers (Iterators) Use two pointers, begin at the start and end at the last character. Compare characters while moving towards the center.

const isPalindrome = (input) => {
  let begin = 0;
  let end = input.length - 1;
  while (begin < end) {
    if (input[begin] !== input[end]) {
      return false;
    }
    begin++;
    end--;
  }
  return true;
};

Method 2: Using a standard For Loop

const isPalindrome = (input) => {
  for (let i = 0; i < input.length / 2; i++) {
    if (input[i] !== input[input.length - 1 - i]) return false;
  }
  return true;
};

Time Complexity: O(N) Auxiliary Space: O(1)

Problem 2: Check if a string is a subsequence of another string

Given two strings s1 and s2, check if s2 is a subsequence of s1. A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Iterative Solution: Use two pointers. Traverse both strings. If characters match, move both pointers. If not, move only the pointer for the first string.

const isSubSeq = (s1, s2, n, m) => {
  let j = 0;
  for (let i = 0; i < n && j < m; i++) {
    if (s1[i] === s2[j]) {
      j++;
    }
  }
  // If we matched all characters of s2, j will be equal to m
  return j === m;
};

Time Complexity: O(N) where N is length of s1. Auxiliary Space: O(1)

Recursive Solution:

const isSubSeqRec = (s1, s2, n, m) => {
  if (m === 0) return true;
  if (n === 0) return false;
  
  if (s1[n - 1] === s2[m - 1]) {
    return isSubSeqRec(s1, s2, n - 1, m - 1);
  }
  return isSubSeqRec(s1, s2, n - 1, m);
};

Time Complexity: O(N) Auxiliary Space: O(N) (due to recursive call stack).

Problem 3: Check for Anagram

Given two strings, check whether they are an anagram of each other. Two strings are anagrams if they are permutations of each other (contain the exact same characters, just in a different order).

Method 1: Sorting Sort both strings. If they are anagrams, the sorted strings will be identical.

const areAnagram = (str1, str2) => {
  if (str1.length !== str2.length) return false;
  
  // Sort both strings
  let s1 = str1.split('').sort().join('');
  let s2 = str2.split('').sort().join('');
  
  return s1 === s2;
};

Time Complexity: O(N log N) Auxiliary Space: O(N) or O(1) depending on the sorting algorithm implementation, but in JS .split() creates arrays taking O(N) space.

Method 2: Frequency Counting (Optimal) Create an array of size 256 (for all ASCII characters) to maintain the frequency of characters. Increment count for characters in the first string and decrement for characters in the second string. If all counts are zero at the end, they are anagrams.

const NO_OF_CHARS = 256;
 
const areAnagramOptimized = (str1, str2) => {
  if (str1.length !== str2.length) return false;
  
  let count = new Array(NO_OF_CHARS).fill(0);
  
  for (let i = 0; i < str1.length; i++) {
    count[str1.charCodeAt(i)]++;
    count[str2.charCodeAt(i)]--;
  }
  
  for (let i = 0; i < NO_OF_CHARS; i++) {
    if (count[i] !== 0) return false;
  }
  
  return true;
};

Time Complexity: O(N) Auxiliary Space: O(1) (Array of size 256 is constant space).

Problem 4: Leftmost Repeating Character

Given a string, find the repeated character present first in the string. For example, in the string "geeksforgeeks", the first repeating character is 'g'.

Method 1: Tracking First Occurrence (Left to Right) Keep track of the first occurrence of every character in an array firstIndex of size 256 initialized to -1. As we traverse from left to right, if the character is seen for the first time, store its index. If it repeats, compare its first index with the current result and update the result if the first index is smaller.

const NO_OF_CHARS = 256;
 
function firstRepeatingLeftToRight(str) {
  let firstIndex = new Array(NO_OF_CHARS).fill(-1);
  let res = Infinity;
  
  for (let i = 0; i < str.length; i++) {
    let charCode = str.charCodeAt(i);
    // If character is seen first time
    if (firstIndex[charCode] === -1) {
      firstIndex[charCode] = i;
    } else {
      // If character repeats, update result with the minimum index
      res = Math.min(res, firstIndex[charCode]);
    }
  }
  return (res === Infinity) ? -1 : res;
}

Time Complexity: O(N) Auxiliary Space: O(1) (Fixed array of size 256).

Method 2: Reverse Traversal (Right to Left) Initialize a visited boolean array of size 256. Traverse the string from right to left. If we see a character we haven't visited, mark it visited. If we see a character that is already visited, update the result index. The last updated result will be our leftmost repeating character.

function firstRepeatingRightToLeft(str) {
  let visited = new Array(NO_OF_CHARS).fill(false);
  let res = -1;
  
  // Traverse from right and update res as soon as we see a visited character
  for (let i = str.length - 1; i >= 0; i--) {
    let charCode = str.charCodeAt(i);
    if (visited[charCode] === false) {
      visited[charCode] = true;
    } else {
      res = i;
    }
  }
  return res;
}

Time Complexity: O(N) Auxiliary Space: O(1)

Problem 5: Reverse Words in a String

Given a string, reverse the order of words. For example, "i love programming very much" should become "much very programming love i".

Algorithm:

  1. Create a temporary array (tmp) to store all words.
  2. Iterate through the string character by character. Add characters to a temporary string (str).
  3. If a space ' ' is encountered, push the current word (str) into the tmp array and reset str to empty.
  4. After the loop, push the last word into the array.
  5. Finally, iterate backwards through the tmp array to construct the reversed output string.
const reverseWords = (s) => {
  let tmp = [];
  let str = "";
  
  // Iterate through the string to extract words
  for (let i = 0; i < s.length; i++) {
    if (s[i] === ' ') {
      tmp.push(str);
      str = "";
    } else {
      str += s[i];
    }
  }
  // Push the last word
  tmp.push(str);
  
  let output = "";
  // Traverse the words array backwards
  for (let i = tmp.length - 1; i > 0; i--) {
    output += tmp[i] + " ";
  }
  // Add the very first word without a trailing space
  output += tmp[0];
  
  console.log(output);
  return output;
};
 
// Example usage:
// reverseWords("i love programming very much");

Time Complexity: O(N) where N is the length of the string. Auxiliary Space: O(N) to store the array of words and the new string.

3. Advanced String Patterns & Scenarios

To crack top-tier technical interviews, you must master these core architectural patterns for strings.

Pattern 1: The Sliding Window

The sliding window technique is used to track a subset of data in an array or string. It's the most common pattern for solving "longest/shortest substring" problems.

Scenario: Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Approach: Use a Set to store the characters in the current window. Use two pointers (left and right). If s[right] is not in the set, add it and expand the window. If it is, remove s[left] and shrink the window from the left until the duplicate is gone.

const lengthOfLongestSubstring = (s) => {
  let charSet = new Set();
  let left = 0;
  let maxLength = 0;
 
  for (let right = 0; right < s.length; right++) {
    // If we find a duplicate, shrink the window from the left
    while (charSet.has(s[right])) {
      charSet.delete(s[left]);
      left++;
    }
    // Add the new character and calculate max length
    charSet.add(s[right]);
    maxLength = Math.max(maxLength, right - left + 1);
  }
  return maxLength;
};

Time Complexity: O(N) Auxiliary Space: O(min(N, M)) where M is the character set size (e.g., 26 or 256).

Pattern 2: Expand From Center (Two Pointers)

While standard two pointers move inwards from the edges, "Expand from Center" is used for finding palindromes within a larger string.

Scenario: Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Approach: A palindrome mirrors around its center. Therefore, a palindrome can be expanded from its center, and there are only 2N - 1 such centers (a center can be a single character, or between two characters for even-length palindromes).

const longestPalindrome = (s) => {
  if (s == null || s.length < 1) return "";
  let start = 0, end = 0;
 
  const expandAroundCenter = (s, left, right) => {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return right - left - 1; // Return length
  };
 
  for (let i = 0; i < s.length; i++) {
    let len1 = expandAroundCenter(s, i, i);     // Odd length
    let len2 = expandAroundCenter(s, i, i + 1); // Even length
    let len = Math.max(len1, len2);
    
    if (len > end - start) {
      start = i - Math.floor((len - 1) / 2);
      end = i + Math.floor(len / 2);
    }
  }
  return s.substring(start, end + 1);
};

Time Complexity: O(N^2) Auxiliary Space: O(1)

Pattern 3: Pattern Searching (Substring Matching)

Searching for a smaller string (pattern) within a larger string (text).

Scenario 1: Naive Pattern Searching

Slide the pattern over the text one by one and check for a match.

const naiveSearch = (text, pattern) => {
  let n = text.length;
  let m = pattern.length;
  let indices = [];
 
  for (let i = 0; i <= n - m; i++) {
    let j;
    for (j = 0; j < m; j++) {
      if (text[i + j] !== pattern[j]) break;
    }
    if (j === m) indices.push(i); // Pattern found at index i
  }
  return indices;
};

Time Complexity: O(N * M)

Scenario 2: KMP (Knuth-Morris-Pratt) Algorithm Overview

The naive approach is slow because it ignores matches done in previous iterations. KMP solves this by pre-processing the pattern to create an LPS (Longest Proper Prefix which is also Suffix) array. This array tells us how many characters to skip, allowing us to find the pattern in O(N + M) time without ever moving the text pointer backwards. (Note: KMP is an advanced algorithm and usually taught in a dedicated module).

Pattern 4: String Parsing and Edge Cases

Interviews often test your ability to handle edge cases (whitespace, signs, integer overflow).

Scenario: String to Integer (atoi)

Convert a string to a 32-bit signed integer. You must handle leading whitespace, a + or - sign, ignore trailing non-digit characters, and clamp the integer to the 32-bit range [-2^31, 2^31 - 1].

Approach: Iterate character by character and build the integer using math (res = res * 10 + digit).

const myAtoi = (s) => {
  let i = 0;
  let sign = 1;
  let res = 0;
  const INT_MAX = 2147483647;
  const INT_MIN = -2147483648;
 
  // 1. Ignore leading whitespace
  while (s[i] === ' ') i++;
 
  // 2. Check sign
  if (s[i] === '-' || s[i] === '+') {
    sign = s[i] === '-' ? -1 : 1;
    i++;
  }
 
  // 3. Read digits
  while (i < s.length && s[i] >= '0' && s[i] <= '9') {
    let digit = s[i] - '0';
    
    // 4. Handle overflow before it happens
    if (res > Math.floor(INT_MAX / 10) || (res === Math.floor(INT_MAX / 10) && digit > 7)) {
      return sign === 1 ? INT_MAX : INT_MIN;
    }
    
    res = res * 10 + digit;
    i++;
  }
 
  return res * sign;
};

Time Complexity: O(N) Auxiliary Space: O(1)

4. The Ultimate String Problem Solving Framework

When facing a String problem in an interview, you can almost always solve it by categorizing it into one of these 7 core patterns. If you are stuck, mentally run through this checklist:

1. The Two-Pointer Technique

Used when you need to compare characters from different parts of a string.

  • Inward Iteration: Moving from ends to the center (e.g., Valid Palindrome, Reverse String).
  • Outward Iteration: Moving from the center to the ends (e.g., Longest Palindromic Substring).
  • Same Direction: Fast and slow pointers (e.g., String Compression, Removing Duplicates).

2. The Sliding Window

Used when the problem asks for the "longest/shortest substring" or a "contiguous sequence" satisfying a specific condition.

  • Fixed Size Window: Checking all substrings of length k (e.g., Find All Anagrams in a String).
  • Variable Size Window: Expanding/shrinking based on a condition (e.g., Longest Substring Without Repeating Characters).

3. Frequency Counting (Hashing)

Used when the problem involves character frequencies, anagrams, or permutations.

  • Use a Fixed Array of size 256 (for ASCII) or a JS Map/Object to store character counts in O(1) space.
  • Classic Examples: Valid Anagram, First Unique Character, Group Anagrams.

4. Dynamic Programming (DP)

Used when the problem asks for the "longest/maximum" involving subsequences (not contiguous) or "minimum cost/operations".

  • Classic Examples: Longest Common Subsequence (LCS), Edit Distance, Longest Palindromic Subsequence.

5. String Parsing & Stacks

Used when the string contains nested structures, mathematical equations, or when you need to match opening/closing sequences.

  • Classic Examples: Valid Parentheses, Decode String, Basic Calculator.

6. Trie (Prefix Tree)

Used heavily in system design or advanced string problems involving dictionary matching, autocomplete, or prefixes.

  • Classic Examples: Implement Trie, Word Search II, Longest Common Prefix.

7. Sorting

While you can't sort a string directly in JavaScript without converting it to an array (str.split('').sort().join('')), sorting is the go-to approach when checking if strings are identical in composition but not order.

  • Classic Example: Group Anagrams (Sort each string and use it as a Hash Map key).
Hash TableAnalysis of Algorithms