sam_2912's blog

Problem: Nice Strings.
By sam_2912, history, 3 years ago, In English

A string of length K is called a nice if the frequency of one of its characters is greater than or equal to floor(K/2). You are given a string s of length N, find the length of longest nice substring.

Input format

  • First line: T number of test cases.

  • For each test case first line contains N, i.e., length of string s and next line contains the string s itself containing only lower case English letters.

Output format

  • For each test case output the length of longest nice substring.

Sample Input

  • 1
  • 5
  • abcde

Sample Output

  • 3

Constraints

  • T <= 10
  • N <= 10^5
  • Vote: I like it
  • +12
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Since I don't have the source and complete test cases of this problem I want to discuss my approach and seek for any better approach.

My approach For every character c from 'a' to 'z', I will assume that c gives the longest nice substring. I can thus convert this problem into finding the longest positive subarray from the array arr[] such that arr[i] == 1 if s[i] == c else arr[i] == -1. Given that an O(N) approach exists for this we are able to solve the problem in essentially O(26*N) time. Is this a right approach given the constraints? Is there a better approach had the character set been much larger than 26?

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

    Actually read the statement once again.

    Suppose n is 5 then frequency of one of its characters should be >=2 in order to satisfy the condition.

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

    Your approach is correct

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      But in this approach

      Suppose string is abc then also it's satisfying the property

      and our array will be 1 -1 -1

      How will we deal with that??

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

        You should find the longest subarray with sum at least -1

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

          I think we can do that with help of binary search and prefix sums.

          Right?

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

            It's not binary searchable as I explained in another comment

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

Binary search + sliding window

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

We can solve it using binary search.

Binary search on value of longest substring and make a corresponding check condition.

For a mid value simply iterate over all mid sized subarrays of string and for each subarray find the max frequency of any character in it and check if it has value >= floor(mid/2)

For finding character with maximum frequency simply u can maintain a set of pairs or there are a lot of other ways too to do this.

Time Complexity: N*(log n*log n)

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

    This property is not monotonic/binary searchable. For example, there are no nice substrings of length 6 in "aabcdeaa", but there is one with length 8.

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

      You are absolutely correct

      Seems like i got upvotes on Wrong Solution lol.

      → Reply