Most Frequent Prefix

Moderate
0/80
profile
Contributed by
1 upvote
Asked in companies
IntuitAdobeUber

Problem statement

You are given a string ‘STR’. Your task is to return a prefix among all the prefixes of ‘STR’ that occurs the maximum number of times as a substring in ‘STR’. In case of a tie, return the longest prefix.

For example: 
You are given ‘STR’ = “ababcd”. Then our answer will be “ab”. The prefixes “a” and “ab” occur the maximum number of times, i.e., 2. As the prefix “ab” is longer than “a” so, our answer will be “ab”.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line contains an integer 'T' which denotes the number of test cases.

The first line of each test case contains a string denoting the input string.
Output Format: 
For each test case, print the prefix among all the prefixes of ‘STR’ that occurs the maximum number of times as a substring in ‘STR’.

The output of each test case will be printed in a separate line.
Constraints: 
1 <= T <= 10 
1 <= STR.LENGTH  <= 5000
‘STR’ contains only lowercase English letters.

Time limit: 1 sec
Note: 
You do not need to input or print anything, as it has already been taken care of. Just implement the given function.
Sample Input 1:
2
ababcd
abcdaabcd
Sample Output 1:
ab
a
Explanation:
For the first test case, you are given ‘STR’ = “ababcd”. Then our answer will be “ab”. The prefixes “a” and “ab” occur the maximum number of times, i.e., 2. As the prefix “ab” is longer than “a” so, our answer will be “ab”.

For the second test case, you are given ‘STR’ = “abcdaabcd”. Then our answer will be “a”. The prefix “a” occur the maximum number of times, i.e., 3.
Sample Input 2:
2
abcdbcd
abcabcc
Sample Output 2:
abcdbcd
abc
Hint

Find the count of every prefix.

Approaches (2)
Brute Force

In this approach, we will find the count of the occurrences of every prefix starting with the smallest one and store it in a variable ‘COUNT’. We will also use the variable ‘MAXCOUNT’ to store the maximum number of times a prefix has occurred. If the current ‘COUNT’ is greater than or equal to ‘MAXCOUNT’, then we will update our answer accordingly. 

 

Algorithm:

  • Initialize a variable 'N' to store the length of 'STR'.
  • Initialize a variable 'MAXCOUNT' to store the maximum number of times a prefix has occurred.
  • Initialize a variable ‘ANS' to store the final output'. The initial value of ‘ANS’ is the first character of ‘STR’.
  • Iterate ‘LEN’ in 1 to ‘N’
    • Initialize a variable 'PREFIX' to store the current prefix of 'STR'.
    • Initialize a variable 'COUNT' to store the number of times the current prefix has occurred in ‘STR’.
    • Iterate ‘I’ in 0 to ‘N’ - ‘LEN’:
      • Initialize a variable ‘J'.
      • Iterate ‘J’ in 0 to ‘LEN’
        • If the character at position (‘I’ + ‘J’) in ‘STR’ is not the same as the character at position ‘J’ in ‘PREFIX.’
          • Break.
      • If ‘J’ is equal to ‘LEN’:
        • Increment ‘COUNT’ by 1.
        • Set ‘J’ as 0.
    • If ‘COUNT’ is greater than or equal to ‘MAXCOUNT.’
      • Set ‘MAXCOUNT’ as ‘COUNT’.
      • Set ‘ANS’ as ‘PREFIX’.
  • Return ‘ANS’.
Time Complexity

O(N ^ 3), where N is the length of the input string ‘STR’.
 

We are iterating through the ‘STR’ using three nested loops, and each loop makes at most N iterations. Hence, the overall time complexity will be O(N ^ 3).

Space Complexity

O(N), where N is the length of the input string ‘STR’.
 

The extra space is used to store the current prefix, which can be as long as ‘STR’. Hence, the overall space complexity is O(N).

Code Solution
(100% EXP penalty)
Most Frequent Prefix
Full screen
Console