String Problem Strategy

28 Oct 2021 in Algorithms

In this post, I would like to talk about several good strategies that you might be able to use for typical string problems. (Only two .. right now.. )

1. Sliding Window
2. Palindrome

Overview

1. Contiguous Substring - Sliding Window

   • Use left and right pointer to expand/trim the window.

   

2. Palindrome - Middle out algorithm

   • Use mid pointer to investigate whether the string is palindromic or not.

   

1. Contiguous Substring - Sliding Window

• Subarray or Contiguous String
  • Use two pointer.
    • Slide your right pointer to the right if the condition is satisfied
    • Slide your left pointer till the condition is satisfied.

  • Template uses double while loop. Move right pointer from outer while loop, and move left pointer from the inner while loop.

  • The condition for this example :

    • Redundant character should not be in a substring.
    • Find maximum length of substring

    

• Template

  public void slidingWindow(String s){
      int left=0; int right =0; int max=0;
      while (right < s.length()){
            
          while (!condition){
              //Shorten window from the left side
              left += 1;
          }
          //Check your target value and update
          int windowSize = right-left+1;
          if(max < windowSize){
              max=windowSize; 
          }
          //Extend window
          right += 1;
      }
      Return max;
  }
  

• Solved - Related Problems

  • Leetcode3) Longest Substring without Repeating Characters - My Solution
  • Leetcode30) Substring with Concatenation of All Words - My Solution
  • Leetcode76) Minimum Window Substring - My Solution
  • Leetcode151) Reverse Words in a String - My Solution
  • Leetcode159) Longest Substring with At Most Two Distinct Characters - My Solution
  • Leetcode340) Longest Substring with At Most K Distinct Characters - My Solution
  • Leetcode424) Longest Repeating Character Replacement - My Solution

2. Palindromic Substring - Middle out

• Palindromic Substrings
  • Expand from the middle,
    • Even length of Palindrome : Use two pointers (mid, mid+1)
    • Odd length of Palindrome : Use one pointer (mid)

  

• Template

  class Solution {
      public boolean Palindrome(String s) {
          int i = s.length()/2;   
            
          if(expandAroundCenter(s, i, i) || expandAroundCenter(s, i, i+1)){
              return true;
          }
          return false;
      }
    
      private boolean expandAroundCenter(String s, int i, int j){
          int Left = i;int Right = j;
    
          while(Left >= 0 && Right < s.length() && s.charAt(Left) == s.charAt(Right)){
              Left --;
              Right ++;
          }
          if(Right == s.length()){
              return true;
          }
          return false;
      }
  }
  

• Solved - Related Problems
  • Leetcode5) Longest Palindromic Substring - My Solution
  • Leetcode 647) Palindromic Substrings - My Solution