Dada una string, encuentre un prefijo con la frecuencia más alta. Si dos prefijos tienen la misma frecuencia, considere el que tiene la longitud máxima.
Ejemplos:
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".
La idea es observar que cada prefijo de la string dada contendrá el primer carácter de la string y el primer carácter solo es también un prefijo de la string dada. Entonces, el prefijo con la ocurrencia más alta es el primer carácter. Ahora queda la tarea de maximizar la longitud del prefijo de frecuencia más alta.
Acercarse :
- Tome un vector que almacenará los índices del primer elemento de la string.
- Si el primer elemento apareció solo una vez, el prefijo más largo será la string completa.
- De lo contrario, haga un bucle hasta la segunda aparición del primer elemento y marque una letra después de cada índice almacenado.
- Si no hay desajuste, avanzamos, de lo contrario, nos detenemos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach #include <bits/stdc++.h> using namespace std; // Function to find Longest prefix string with the // highest frequency void 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 Code int main() { string str = "abcab"; prefix(str); return 0; }
Java
// Java implementation of the above approach import 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 approach using 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>
Producción:
ab
Complejidad de tiempo : O(N)
Publicación traducida automáticamente
Artículo escrito por rishigarg0709 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA