A Python template to solve most problems involving substrings using a two-pointer approach.

DSA_SubstringTemplate.py

"""
A Python template to solve most problems involving substrings using a two-pointer approach.
Template based on this post: https://leetcode.com/problems/minimum-window-substring/discuss/26808/Here-is-a-10-line-template-that-can-solve-most-'substring'-problems
"""
def substring(string: str) -> int:
  counter = int()  # To check if the substring is valid
  left, right = 0, 0  # Two pointers, right pointer is exclusive
  length = int()  # Length of the substring
  map = dict()  # Intialize the hash map here, collections.Counter is useful
  
  while (right < len(str)):
    # Include next character
    if string[right] in map:
      if map[string[right]] > ?:
        counter = ?  # Modify counter here
      map[string[right]] -= 1
    right += 1  # Move to the next character
    
    # Shorten substring while condition
    while (?):  # Counter condition
      # Substring is valid based on condition, substring length is (right-left)
      # Update the length here if finding miniumum
      # Increase from left until the substring becomes invalid
      if string[left] in map:
        map[s[left]] += 1
        if map[s[left]] > ?:
          counter = ?  # Modify counter here
      # Update the length here if finding maximum
 
  return length

"""
Example usage of template
Problem: https://leetcode.com/problems/minimum-window-substring/
Solution: https://github.com/siddharthapdutta/August-LeetCoding-Challenge-2021/blob/master/Minimum%20Window%20Substring.py
"""