Here are some standard types of questions on a string that one faces in their coding journey and how to think of approaching any string-based question by categorizing them into 5 types.

1. Type I: When it is required to validate the string or to find something in the string. In such questions, it is required to traverse the string like an array whilst validating or finding something.

   Problems of this type:

   • [ ] Valid Parentheses
   • [ ] Valid Number
   • [ ] Compare Version Numbers

2. Type II When you need to search a substring/another string. Most of such questions can be solved using pointer-based approach. One/more pointer approach.

   Problems of this type:

   • [ ] Longest Substring Without Repeating Characters
   • [ ] Implement strStr()
   • [ ] Substring with Concatenation of All Words
   • [ ] Valid Palindrome
   • [ ] Replace the Substring for Balanced String

3. Type III When you need to find the smallest/largest/ conditional substring from the given string, the sliding window approach is the way to go. An example of such a question would be: find the longest substring without repeating the character.

   Problems on this type:

   • [ ] Minimum Window Substring
   • [ ] Maximum Number of Vowels in a Substring of Given Length
   • [ ] Longest Substring with At Most Two Distinct Characters (LC Premium)
   • [ ] Longest Substring with At Most K Distinct Characters (LC Premium)

4. Type IV When the problem needs you to find all the permutations of a string, backtracking is the most common approach for such problems.

   Problems on this type:

   • [ ] Split Array into Fibonacci Sequence
   • [ ] Regular Expression Matching
   • [ ] Letter Combinations of a Phone Number
   • [ ] Restore IP Addresses

5. Type V Whenever the above approaches do not fit, its most likely a question on Dynamic Programming. Try to identify the subproblem and solve using DP.

   Problems on this type:

   • [ ] Longest Palindromic Substring
   • [ ] Longest Valid Parentheses
   • [ ] Wildcard MatchingEdit Distance

• Template to find substring:

• Some more categories of problems on substrings :