bootcoder's blog

Question on substring
By bootcoder, history, 3 years ago, In English

There is a string s of length n , we have to find the maximum length x such that all substrings L of length x has at most k distinct characters.

constraint- n<=10^5

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

Comments Comments (3)
| Write comment?
»
3 years ago, # |
  Vote: I like it -19 Vote: I do not like it
Hint
Hint incase testcases are not that strong
→ Reply
»
3 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Binary search for length of substring + use sliding window for checking count of distinct characters in each window.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    No need for binary search, you can just use sliding window and take min length of each "window" before shifting one of the pointers (depending on which way you do it).

    → Reply