Can anybody explain the solution to this interesting string-problem based on optimization ?

general
, , ,
1

This is a problem from previous contest : https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/superior-substring-dec-circuits-e51b3c27/

Problem-Statement :—>

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 ‘t’ that represents the total number of test cases

For each test case:

First line: Integer ‘n’ that represents the length of the string

Next line: String ‘S’ of the length ‘N’

Output format :

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

Constraints :
1<=T<=10

1<=N<=10^5

The string contains only lowercase English alphabets.

2

Note:–>

I made lot(s) of optimization(s) to the O(n^2) method , but , it still doesn’t pass all the cases and about the binary search algorithm, I am not getting it :frowning:

3

Hi,
Here is a quick explanation of how I solved this in linear time - Yes, this one can be done better than your expected O(N log(N)) running time.

  1. First we notice that the string only contains alphabet letters so we can process 1 letter at a time. For example abcabc. If we consider letter ‘a’ first, it looks like a==a== and the longest superior substring has length 5. Similarly, for letter ‘b’, =b==b=, it also has longest length 5. As there are 26 letters, your first loop will be from in range 26.

  2. Now, how are we gonna decide the longest superior substring for a single letter? For example, we consider letter ‘a’ of this string: ‘==aa====aaa==a’. Let consider each connected ‘a’ as a group or we can call them islands of ‘a’. The string above has 1 island of length 2, follow by 1 island of length 3 and finally 1 island of length 1. Each island of length l can be extended left/right by l + 1 to remain a superior substring. If it needed less than l + 1 to connected to another island then it will have more ‘letters’ to spare. Using this idea you can process it greedily and keep the information of the visited islands from left to right.

1 Like
4

I understand the approach,first of all, thanks for answering :slight_smile: In the second part,you mention about how to process those islands,and check if they can be increased from themselves to left/right, but if we do this for every island then,things can time out, so should i just check how far the largest island can be increased and consider it as my final answer for that ‘alphabet’? Thanks !:slight_smile: