How can I solve this string optimization problem ?

Правка en2, от LovesProgramming, 2019-01-21 19:44:06

You are given a string of length 'n'.

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. 5/2=2 , etc.

The string contains only lowercase English alphabets.

I have tried O(n^2) solution(s) with some optimization(s) which obviously got timed out. I realized that there are better:- O(nlogn) or O(n) approaches,can anybody explain them?

Link to the problem statement :- https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/superior-substring-dec-circuits-e51b3c27/

Thanks :-)

Теги string, complexity optimization

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский LovesProgramming 2019-01-21 19:44:06 9 Tiny change: 'there are O(nlogn) ' -> 'there are better:- O(nlogn) '
en1 Английский LovesProgramming 2019-01-21 19:43:06 857 Initial revision (published)