Given a string, find a prefix with the highest frequency. If two prefixes have the same frequency then consider the one with the maximum length.
Examples:
Input : str = "abc" Output : abc Each prefix has same frequency(one) and the prefix with maximum length is "abc". Input : str = "abcab" Output : ab Both prefix "a" and "ab" occur two times and the prefix with maximum length is "ab".
The idea is to observe that every prefix of the given string will contain the first character of the string in it and the first character alone is also a prefix of the given string. So the prefix with the highest occurrence is the first character. The task now remains to maximize the length of the highest frequency prefix.
Approach :
- Take a vector that will store the indices of the first element of the string.
- If the first element appeared only once, then the longest prefix will be the whole string.
- Otherwise, loop till the second appearance of the first element and check one letter after every stored index.
- If there is no mismatch we move forward otherwise we stop.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;// Function to find Longest prefix string with the // highest frequencyvoid prefix(string str){ int k = 1, j; int n = str.length(); vector<int> g; int flag = 0; // storing all indices where first element is found for (int i = 1; i < n; i++) { if (str[i] == str[0]) { g.push_back(i); flag = 1; } } // if the first letter in the string does not occur // again then answer will be the whole string if (flag == 0) { cout << str << endl; } else { int len = g.size(); // loop till second appearance of the first element while (k < g[0]) { int cnt = 0; for (j = 0; j < len; j++) { // check one letter after every stored index if (str[g[j] + k] == str[k]) { cnt++; } } // If there is no mismatch we move forward if (cnt == len) { k++; } // otherwise we stop else { break; } } for (int i = 0; i < k; i++) { cout << str[i]; } cout << endl; }}// Driver Codeint main(){ string str = "abcab"; prefix(str); return 0;} |
Java
// Java implementation of the above approachimport java.util.*;class GFG{ // Function to find Longest prefix string with the // highest frequency static void prefix(char[] str) { int k = 1, j; int n = str.length; Vector<Integer> g = new Vector<>(); int flag = 0; // storing all indices where first element is found for (int i = 1; i < n; i++) { if (str[i] == str[0]) { g.add(i); flag = 1; } } // if the first letter in the string does not occur // again then answer will be the whole string if (flag == 0) { System.out.println(String.valueOf(str)); } else { int len = g.size(); // loop till second appearance of the first element while (k < g.get(0)) { int cnt = 0; for (j = 0; j < len; j++) { // check one letter after every stored index if ((g.get(j) + k) < n && str[g.get(j) + k] == str[k]) { cnt++; } } // If there is no mismatch we move forward if (cnt == len) { k++; } // otherwise we stop else { break; } } for (int i = 0; i < k; i++) { System.out.print(str[i]); } System.out.println(); } } // Driver Code public static void main(String args[]) { String str = "abcab"; prefix(str.toCharArray()); }}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of the above approach # Function to find Longest prefix string with the # highest frequency def prefix(string) : k = 1; n = len(string); g = []; flag = 0; # storing all indices where first element is found for i in range(1, n) : if (string[i] == string[0]) : g.append(i); flag = 1; # if the first letter in the string does not occur # again then answer will be the whole string if (flag == 0) : print(string); else : length = len(g); # loop till second appearance of the first element while (k < g[0]) : cnt = 0; for j in range(length) : # check one letter after every stored index if (string[g[j] + k] == string[k]) : cnt += 1; # If there is no mismatch we move forward if (cnt == len) : k += 1; # otherwise we stop else : break; for i in range(k+1) : print(string[i],end=""); print() # Driver Code if __name__ == "__main__" : string = "abcab"; prefix(string); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the above approachusing System;using System.Collections.Generic; class GFG{ // Function to find Longest prefix string with the // highest frequency static void prefix(char[] str) { int k = 1, j; int n = str.Length; List<int> g = new List<int>(); int flag = 0; // storing all indices where first element is found for (int i = 1; i < n; i++) { if (str[i] == str[0]) { g.Add(i); flag = 1; } } // if the first letter in the string does not occur // again then answer will be the whole string if (flag == 0) { Console.WriteLine(String.Join("",str)); } else { int len = g.Count; // loop till second appearance of the first element while (k < g[0]) { int cnt = 0; for (j = 0; j < len; j++) { // check one letter after every stored index if ((g[j] + k) < n && str[g[j] + k] == str[k]) { cnt++; } } // If there is no mismatch we move forward if (cnt == len) { k++; } // otherwise we stop else { break; } } for (int i = 0; i < k; i++) { Console.Write(str[i]); } Console.WriteLine(); } } // Driver Code public static void Main() { String str = "abcab"; prefix(str.ToCharArray()); }}// This code contributed by Rajput-Ji |
Javascript
<script>// Javascript program for the above approach // Function to find Longest prefix string with the // highest frequency function prefix(str) { let k = 1, j; let n = str.length; let g = []; let flag = 0; // storing all indices where first element is found for (let i = 1; i < n; i++) { if (str[i] == str[0]) { g.push(i); flag = 1; } } // if the first letter in the string does not occur // again then answer will be the whole string if (flag == 0) { document.write((str.join(""))); } else { let len = g.length; // loop till second appearance of the first element while (k < g[0]) { let cnt = 0; for (j = 0; j < len; j++) { // check one letter after every stored index if ((g[j] + k) < n && str[g[j] + k] == str[k]) { cnt++; } } // If there is no mismatch we move forward if (cnt == len) { k++; } // otherwise we stop else { break; } } for (let i = 0; i < k; i++) { document.write(str[i]); } document.write("<br/>"); } }// Driver Code let str = "abcab"; prefix(str); // This code is co tributed by sanjoy_62.</script> |
Output:
ab
Time Complexity: O(N), where N is the length of the given string.
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
