Proficient Level
Implement the minimumWindowContainsPatternLength method that returns the length of the smallest substring containing all pattern characters.
The input contains two strings: text and pattern. Your task is to find the length of the smallest substring in text that contains every character required by pattern.
Characters must be counted correctly. For example, if the pattern contains two a characters, the selected window must also contain at least two a characters. If no valid substring exists, return 0.
Example 1
Input
text (string) =
ADOBECODEBANCpattern (string) =
ABCReturns (int)
4Example 2
Input
text (string) =
apattern (string) =
aReturns (int)
1Example 3
Input
text (string) =
apattern (string) =
aaReturns (int)
0Use the sliding window technique with frequency counts.
First count how many times each character is required from pattern. Then expand the right side of the window over text and update the count of matched characters.
When the current window contains all required characters, try to shrink it from the left side. Each time the window is valid, update the minimum length.
Pseudocode:
function minimumWindowContainsPatternLength(text, pattern):
if pattern is empty or text is shorter than pattern:
return 0
required = frequency map of pattern characters
window = empty frequency map
formed = 0
need = number of unique characters in required
left = 0
best = infinity
for right from 0 to length(text) - 1:
add text[right] to window
if text[right] count matches required count:
formed++
while formed == need:
best = min(best, right - left + 1)
remove text[left] from window
if text[left] count becomes less than required count:
formed--
left++
if best is infinity:
return 0
return bestReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run