rezzaque's blog

How to find the minimum range including all characters of a string?
By rezzaque, history, 8 years ago, In English

Given a string s with size n, how do I find the minimun range (p,q) such that all the characters in s occur in that range. Looking for an O(n) solution.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

First hash the characters of string then use two pointer approach.

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

first you find out the number of different characters in the given string using hashing.. . Now you have to find out the smallest window in the given string such that it contains all distinct characters.

val=no.of distinct characters.

now to do this you can use two pointer technique.. how?? take st=0 (left point of window) and take i=0 (right point of window initially) . keep adding characters till count of distinct is less than val.. (my variable is cur) as soon as you reach cur = val then you try to remove characters from back to reduce window size making sure that your cur is equal to value.. so u shift st for that.. as you have shifted st to the point where you could now add a character each time and remove characters from back each time and check current window size for minimum.. you will get it when you work out on paper.. if you still have some doubts let me know.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I actually came up with two solutions one of them is really similar to this. However, I am not sure if your solution can handle the case where the character at st does not occur again in a short range. That is, you always count the number of distinct characters but left endpoint can decrease that when shifted, how will your algorithm respond to that?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For each window keep the frequency of each characters present in it and keep the count of no of characters having frequency greater than 0. If this value comes out to be no of distinct characters in the string, then consider that range for answer.

      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I came up with two solutions for this question lately.

1--> *I determine distinct elements by hashing in O(n) time. *I take the indices of all characters from the original string using different stacks for all distinct characters. *I start eleminating them from start as they are sorted(by nature as we start from the beginning of the string) and look for the minimum range in every step. *I output the minimum range.

2--> *I determine distinct elements by hashing in O(n) time. *Create an array a[] that has a size of the number of distinct characters. *I start from the beginning of the string s and increase the number of occurrence of character s[i] in a. That is; a[s[i]]++; *When I first reach to a state that all of the distinct elements have occurred at least once, I look for the left endpoint and if the character there has a number of occurrence(a[s[left_endpoint]]) more than 1 than I can reduce that. *I repeat while(a[s[left_endpoint]]>1) *Then I reduce the left endpoint to see if I can have different substrings on the right that has the expected property.

It also takes O(n) time.

If you see a problem please inform me, thank you!

→ Reply