Finding number of Unique strings in wraparound string ~ Programming Ninja

Given a string s which is an infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so s will look something like this: "...zaabcdefghijklmnopqrstuvwxyzabc...". Now we have another string s2. We need to find the number of unique non-empty substringsof s2 which are present in s.

s: yzabc

s2: abc

result: 6

Solution:

We can see here that all the characters of the string s are in increasing order, except for the case where we have "za", to include this case we can use modular operation with 26, Now we have to only check how many strings are there which are in increasing order in s2.

To check this we create an alphabet array of size 26, where alphabet[i] stores the maximum length of substring ending with character number i (i.e, a, i=0).

We maintain a variable 'len' which stores current maximum length of the string. At any point where we find that the string is not in increasing order, we make 'len' 0.

Now our string has an interesting property

we see that having "abcd" implies having "bcd", which implies having "cd", which implies having "d". In other words, you cannot have the substring "abcd" but not have the substring "d", since one necessarily implies the other.

Now we see that there is a connection between the number of elements in this subset and the length of its longest element: the size of the subset is the length of its longest element. In particular, if the longest substring ending in d that we find is "abcd", then we can confidently say that there are 4 substrings that end in d.

This means that if we want to find all the possible substrings that end in a particular character (i.e. d) in s2, then we only need to find the longest substring in s2 that ends with d and take its length.

Code:

int findSubstring(string s2) {

if(s2.length()==0)

return 0;

int ans=0,len=0;

vector<int> alphabets(26,0);

for(int i=0;i<s2.length();i++)

{

if(i>0&&(s2[i]-'a')%26!=(s2[i-1]-'a'+1)%26)

len=0;

len++;

if(len>alphabets[p[i]-'a']){

ans+=len-alphabets[p[i]-'a'];

alphabets[p[i]-'a']=len;}

}

return ans;

}

Do share this post if you found it helpful and comment if you have some new insights about the problem

Happy Programming

About Home

Programming ninja