Most Frequent Prefix

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’.

We know that prefix is the leading contiguous part of a string. A prefix always starts from the first character of the string. Hence, we can say that the first character alone is the prefix that occurs maximum times in the string because all the string prefixes will contain the first character. But a prefix may exist that occurs as many times as the first character and has a greater length. In that case, the longer prefix will be our answer. 

For example, if the given ‘STR’ is ‘ababcd’, the prefixes “a” and “ab” occur the maximum number of times, i.e., 2. But our answer is “ab” because “ab” is longer than “a”.

If the length of our answer is K, then all the occurrences of the first character must be followed immediately by the same K - 1 characters. So, to find the longest prefix that occurs the maximum number of times, we will maintain a list of occurrences of the first character and check the following characters, moving forward from every occurrence of the first character until any mismatch happens. Suppose if the mismatch happens at position ‘POS’, then the substring ‘STR[0:’POS’ - 1] will be our answer.

Algorithm:

• Initialize a variable 'N' to store the length of 'STR'.
• Initialize an integer array 'FIRSTCHARPOS' to store the positions where the character is the same as the first character in ‘STR’.
• Initialize a variable 'FIRSTCHAROCCUR' to store the number of times the first character occurs in 'STR'.
• Iterate ‘I’ in 0 to ‘N’:
  • If the ‘I’th character in ‘STR’ is the same as the first character in ‘STR’:
    • Set  'FIRSTCHARPOS['FIRSTCHAROCCUR']’ as ‘I’.
    • Increment 'FIRSTCHAROCCUR' by 1.
• If 'FIRSTCHAROCCUR' is equal to 1, return ‘STR’.
• Initialize a variable 'POS.'
• Initialize a variable ‘POSTCHAR’.
• Iterate while ‘POSTCHAR’ is true and (‘POS’ + 1) is less than ‘N’.
  • Increment ‘POS’ by 1.
  • Initialize a variable ‘CUR’ to store the current character of ‘STR’.
  • Iterate ‘J’ in 0 to 'FIRSTCHAROCCUR'
    • If ('FIRSTCHARPOS[‘J']’ + ‘POS’) is greater than ‘N’ or ‘CUR’ is not equal to the character at position (('FIRSTCHARPOS[‘J']’ + ‘POS’)) in ‘STR’:
      • Set ‘POSTCHAR’ as false.
• Return Substring of ‘STR’ from index 0 to ‘POS’(Exclusive).