SubString Problems
-- Overview
This substring topic is very related to two pointer technique, which is also a topic that may need to utilize sliding window problem. So Let's dive in those problem and, hopefully, get comfortable with many examples.
-- Examples
1. Determine If One String Is Another's Substring
Determine if a small string is a substring of another large string.
Return the index of the first occurrence of the small string in the large string.
Return -1 if the small string is not a substring of the large string.
Assumptions
- Both large and small are not null
- If small is empty string, return 0
Examples
- “ab” is a substring of “bcabc”, return 2
- “bcd” is not a substring of “bcabc”, return -1
- "" is substring of "abc", return 0
Note: two loop with 3 base cases:
1. if we reach the end of needle, then return the index in big string.
2. if we reach the end of big string, but still not find any match, we return -1, meaning not exist.
3. Else we check the current position to big, and small string, see if we have a match, if not we break this inner loop.
2. Longest Substring Without Repeating Characters
Given a string, find the longest substring without any repeating characters and return the length of it. The input string is guaranteed to be not null.
For example, the longest substring without repeating letters for "bcdfbd" is "bcdf", we should return 4 in this case.
Note: It is a typical, classic, Sliding window algorithm applied to a subString problem.
3.1 : Longest SubString with at most 2 distinct
Given a string, find the length of the longest substring T that contains at most 2 distinct characters.
For example, Given s =
“eceba”,
T is "ece" which its length is 3.
Note: If you really understand example 2, and this 3.1 example, you may find out that the only difference of this two problem, when we use sliding window algorithm to solve it, is how we move our start pointer to let the substring in our window size is a valid substring according to the question requirement.
3.2 : Longest SubString with at most K distinct
Given a string, find the length of the longest substring T that contains at most k distinct characters.
For example, Given s =
“eceba” and k = 2,
T is "ece" which its length is 3.
Note: Compare 3.1 and 3.2, we only need to change the condition when we should shrink our window.
Also, notice from line 17 - 19, we only decrement the count of distinct value, if we gonna decrement on a value 1 char on our map, but for every char start pointer is passing, we do need to decrement its map value.
4. Longest palindrome subString
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example:
Input: "babad" Output: "bab" Note: "aba" is also a valid answer.
Example:
Input: "cbbd" Output: "bb"
Note: It is little abstract if you are not that familiar with DP, but here is a diagram to explain the man flow of the idea:
The read arrow in the cell means we will look the previous dp[i+1][j-1] to determine the value of this current cell. and if dp[i][j] = true, means the substring start at index i, ends at index j , is a valid palindrome.
5. Find all Anagrams in one String
Find all occurrence of anagrams of a given string s in a given string l. Return the list of starting indices.
Assumptions
- s is not null or empty.
- l is not null.
Examples
- l = "abcbac", s = "ab", return [0, 3] since the substring with length 2 starting from index 0/3 are all anagrams of "ab" ("ab", "ba").
Note:In this problem, we keep our window size = s.length(), and after ( i >= window size ) every time we move forward one character , we also take care of the one that was at end of our window size. Notice that the condition that we do ( match++, or math-- ), is the same as we did in Example 3.
-- Only if we will decrement on a count number = 1 --> match++
-- Only if we will increment on a count number = 0 --> match--
Hope you get some experience to deal with other similar substring problems.
Happy Coding -_-
Ye Jiang
Happy Coding -_-
Ye Jiang
