Superior Substring

3.7

81 votes
Algorithms, Binary Search, Easy, Hash Maps, Searching, Sorting, String Manipulation
Problem

You are given a string of length . If a string contains at least one character whose frequency is greater than or equal to the half of the length of the string, then the string is called superior.

You are required to find the length of the longest superior substring available in the given string .

Note: Here half is considered under integer division i.e. , etc.

Input format

  • First line: Integer  that represents the total number of test cases
  • For each test case:
    • First line: Integer  that represents the length of the string  
    • Next line: String of the length

Output format

For each test case, print the length of the longest superior substring in a new line.

Constraints



The string contains only lowercase English alphabets.

Sample Input
2
5
abcde
14
ababbbacbcbcca
Sample Output
3
13
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

Sample test case : We can select the substring starting from index to , here the frequency of is which is greater than or equal to .
Note that, there can be multiple possible substrings.

Editor Image

?