[AlgoMastery]
Topics›String›Longest Substring Problems
📖

Longest Substring Problems

String
~20 min read
5 practice problems

Overview

Longest substring problems are a class of string algorithms that ask you to find the longest contiguous substring satisfying a specific condition. These problems are typically solved using the sliding window technique, making them excellent practice for mastering that pattern.

Common variations include:

  • Longest substring without repeating characters
  • Longest substring with at most K distinct characters
  • Longest palindromic substring
  • Longest substring with same characters after K replacements

Pattern 1: Longest Substring Without Repeating Characters

Find the longest substring where all characters are unique.

Approach: Use sliding window with a Set to track characters in the current window.

function lengthOfLongestSubstring(s: string): number {
  const seen = new Set<string>();
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    // Shrink window until no duplicate
    while (seen.has(s[right])) {
      seen.delete(s[left]);
      left++;
    }
    
    seen.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

Optimized version using Map to store last index:

function lengthOfLongestSubstringOptimized(s: string): number {
  const lastIndex = new Map<string, number>();
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    
    // Jump left pointer if duplicate found
    if (lastIndex.has(char) && lastIndex.get(char)! >= left) {
      left = lastIndex.get(char)! + 1;
    }
    
    lastIndex.set(char, right);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

Time: O(n), Space: O(min(n, alphabet size))

Pattern 2: Longest Substring with At Most K Distinct Characters

Find the longest substring containing at most K different characters.

function lengthOfLongestSubstringKDistinct(s: string, k: number): number {
  const freq = new Map<string, number>();
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    freq.set(char, (freq.get(char) || 0) + 1);
    
    // Shrink window if distinct count exceeds k
    while (freq.size > k) {
      const leftChar = s[left];
      freq.set(leftChar, freq.get(leftChar)! - 1);
      if (freq.get(leftChar) === 0) {
        freq.delete(leftChar);
      }
      left++;
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

Time: O(n), Space: O(k)

Pattern 3: Longest Palindromic Substring

Find the longest substring that reads the same forward and backward.

Approach: Expand around center for each possible center position.

function longestPalindrome(s: string): string {
  let start = 0;
  let maxLen = 0;
  
  function expandAroundCenter(left: number, right: number) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    const len = right - left - 1;
    if (len > maxLen) {
      maxLen = len;
      start = left + 1;
    }
  }
  
  for (let i = 0; i < s.length; i++) {
    expandAroundCenter(i, i);     // Odd length palindromes
    expandAroundCenter(i, i + 1); // Even length palindromes
  }
  
  return s.substring(start, start + maxLen);
}

Time: O(n²), Space: O(1)

Dynamic Programming approach:

function longestPalindromeDP(s: string): string {
  const n = s.length;
  const dp: boolean[][] = Array(n).fill(null).map(() => Array(n).fill(false));
  let start = 0;
  let maxLen = 1;
  
  // Single characters are palindromes
  for (let i = 0; i < n; i++) {
    dp[i][i] = true;
  }
  
  // Check for length 2
  for (let i = 0; i < n - 1; i++) {
    if (s[i] === s[i + 1]) {
      dp[i][i + 1] = true;
      start = i;
      maxLen = 2;
    }
  }
  
  // Check for length 3 and more
  for (let len = 3; len <= n; len++) {
    for (let i = 0; i < n - len + 1; i++) {
      const j = i + len - 1;
      if (s[i] === s[j] && dp[i + 1][j - 1]) {
        dp[i][j] = true;
        start = i;
        maxLen = len;
      }
    }
  }
  
  return s.substring(start, start + maxLen);
}

Time: O(n²), Space: O(n²)

Pattern 4: Longest Substring with Same Characters After K Replacements

Find the longest substring where you can replace at most K characters to make all characters the same.

function characterReplacement(s: string, k: number): number {
  const freq = new Map<string, number>();
  let left = 0;
  let maxCount = 0; // Most frequent character in current window
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    freq.set(char, (freq.get(char) || 0) + 1);
    maxCount = Math.max(maxCount, freq.get(char)!);
    
    // Shrink if replacements needed exceed k
    // Window size - maxCount = characters to replace
    while (right - left + 1 - maxCount > k) {
      freq.set(s[left], freq.get(s[left])! - 1);
      left++;
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

Key insight: We don't need to update maxCount when shrinking because we only care about the maximum window size, and shrinking won't increase maxCount.

Time: O(n), Space: O(1) for fixed alphabet

Pattern 5: Longest Substring with At Least K Repeating Characters

Find the longest substring where every character appears at least K times.

Approach: Divide and conquer - if a character appears less than K times, split on that character.

function longestSubstring(s: string, k: number): number {
  if (s.length < k) return 0;
  
  const freq = new Map<string, number>();
  for (const char of s) {
    freq.set(char, (freq.get(char) || 0) + 1);
  }
  
  // Find first character with frequency < k
  for (let i = 0; i < s.length; i++) {
    if (freq.get(s[i])! < k) {
      // Split on this character
      const left = longestSubstring(s.substring(0, i), k);
      const right = longestSubstring(s.substring(i + 1), k);
      return Math.max(left, right);
    }
  }
  
  // All characters appear at least k times
  return s.length;
}

Time: O(n²) worst case, Space: O(n) for recursion

Common Variations

Variation 1: Longest Substring with Balanced Characters

Find longest substring with equal count of two characters.

function longestBalancedSubstring(s: string, char1: string, char2: string): number {
  let count1 = 0, count2 = 0;
  let maxLen = 0;
  
  for (let i = 0; i < s.length; i++) {
    count1 = 0;
    count2 = 0;
    
    for (let j = i; j < s.length; j++) {
      if (s[j] === char1) count1++;
      if (s[j] === char2) count2++;
      
      if (count1 === count2 && count1 > 0) {
        maxLen = Math.max(maxLen, j - i + 1);
      }
    }
  }
  
  return maxLen;
}

Variation 2: Longest Substring with Vowels in Even Counts

Find longest substring where each vowel appears an even number of times.

function longestSubstringWithEvenVowels(s: string): number {
  const vowels = 'aeiou';
  const vowelMask: Record<string, number> = {
    'a': 1, 'e': 2, 'i': 4, 'o': 8, 'u': 16
  };
  
  const firstOccurrence = new Map<number, number>();
  firstOccurrence.set(0, -1);
  
  let mask = 0;
  let maxLen = 0;
  
  for (let i = 0; i < s.length; i++) {
    const char = s[i].toLowerCase();
    if (vowels.includes(char)) {
      mask ^= vowelMask[char]; // Toggle bit
    }
    
    if (firstOccurrence.has(mask)) {
      maxLen = Math.max(maxLen, i - firstOccurrence.get(mask)!);
    } else {
      firstOccurrence.set(mask, i);
    }
  }
  
  return maxLen;
}

Time: O(n), Space: O(1)

When to Use These Patterns

Use longest substring techniques when:

  • Problem asks for "longest substring" satisfying a condition
  • Condition can be checked locally (within the substring)
  • Sliding window is applicable (contiguous segment)
  • You need to track character frequencies or distinct counts

Template

function longestSubstringTemplate(s: string, condition: any): number {
  const window = new Map(); // or Set, or array
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    // Add s[right] to window
    // Update tracking structure
    
    // Shrink if condition violated
    while (/* condition violated */) {
      // Remove s[left] from window
      left++;
    }
    
    // Update maxLen (window is now valid)
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

Time and Space Complexity

  • Time: O(n) for sliding window approaches, O(n²) for expand-around-center
  • Space: O(k) where k is distinct characters or alphabet size

Practice Tips

  1. Identify the condition — What makes a substring valid?
  2. Choose tracking structure — Set for uniqueness, Map for frequencies
  3. Optimize shrinking — Sometimes you can jump left pointer instead of shrinking one by one
  4. Handle edge cases — Empty string, all same characters, k = 0
  5. Consider divide-and-conquer — For "at least K" type problems

Related Concepts

  • Sliding Window — Core technique for most longest substring problems
  • Two Pointers — Used in expand-around-center for palindromes
  • Character Frequency Maps — Essential for tracking window state
  • Dynamic Programming — Alternative approach for palindromic substrings

Longest substring problems are excellent for practicing sliding window and frequency counting. Master these patterns, and you'll be well-prepared for similar interview questions.

← PreviousString ParsingNext →Substring Search