PROBLEM LINK:
Editorialist: Karan Aggarwal
DIFFICULTY:
CAKEWALK
PREREQUISITES:
Strings
PROBLEM:
Given 2 string L and K of length N and N-1 respectively, tell whether K can be formed by removing exactly 1 character from L.
EXPLANATION:
This problem can be reduced to a more general problem of given 2 string, find whether one is a sub-sequence of other.
This can be done in O(N) by keeping a track of how much of the smaller string K has been seen till now in the bigger string L.
Let seen represent the length K seen in L[0…i-1]
seen = 0; for(int i=0; i< N; i++) if(K[seen] == L[i]) seen = seen+1
If seen == N-1 in the loop, then we string K is a sub-sequence of string L .
Complexity : O(N)