PROBLEM LINKS:
Author: sikander_nsit
Tester: sikander_nsit
Editorialist: sikander_nsit
DIFFICULTY:
SIMPLE-EASY
PROBLEM:
Given a string consisting of three possible characters ‘B’, ‘R’ and ‘G’ find the length of the shortest substring such that it contains all three characters atleast once.
EXPLANATION:
This was an implementation based problem. There are numerous ways to do it. One way is to traverse the string and for each position calculate the answer if the substring ended at the current position. For this we can keep three variables to keep track of the most recent position of each pill. At each position update the most recent position of the current pill as the current index and calculate the answer by subtracting from this the minimum of the three values.
PSEUDOCODE
arr['R']=arr['G']=arr['B']=-10000000;
for(j=0;j<n;++j)
{
arr[str[j]]=j;
num=j-min(arr['R'],min(arr['G'],arr['B']))+1;
ans=min(ans,num);
}
AUTHOR’S SOLUTION:
Author’s solution can be found here.