### sam_2912's blog

By sam_2912, history, 7 days ago,

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

• +12

 » 7 days ago, # | ← Rev. 2 →   +3 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?
•  » » 7 days ago, # ^ |   0 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.
•  » » » 7 days ago, # ^ |   0 Yeah right! Won't work given the "or equal" condition.
•  » » 7 days ago, # ^ |   0 Your approach is correct
•  » » » 7 days ago, # ^ | ← Rev. 2 →   +10 But in this approach Suppose string is abc then also it's satisfying the propertyand our array will be 1 -1 -1How will we deal with that??
•  » » » » 7 days ago, # ^ |   0 You should find the longest subarray with sum at least -1
•  » » » » » 7 days ago, # ^ |   +10 I think we can do that with help of binary search and prefix sums.Right?
•  » » » » » » 7 days ago, # ^ |   0 It's not binary searchable as I explained in another comment
•  » » » » » » 7 days ago, # ^ |   0 Yes. We can tweak this a bit to account for >= k. It has a complexity of O(n log n).
 » 7 days ago, # |   0 Binary search + sliding window
 » 7 days ago, # |   +10 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)
•  » » 7 days ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 7 days ago, # ^ |   0 You are absolutely correct Seems like i got upvotes on Wrong Solution lol.