Open In App

Python | Count all prefixes in given string with greatest frequency

Last Updated : 18 Jan, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Given a string, print and count all prefixes in which first alphabet has greater frequency than second alphabet.
Take two alphabets from the user and compare them. The prefixes in which the alphabet given first has greater frequency than the second alphabet, such prefixes are printed, else the result will be 0. 

Examples : 

Input : string1 = "geek", 
        alphabet1 = "e", alphabet2 = "k"
Output :
ge
gee
geek
3

Input : string1 = "geek",
        alphabet1 = "k", alphabet2 = "e"
Output :
0

Approach: Take an empty string to store the string values of all the prefixes formed. Then check for the alphabet with greater frequency than the second alphabet. If no such case is found then the result will be 0 prefixes.

Implementation:

Python3




# Python program to Count all
# prefixes in given string with
# greatest frequency
 
# Function to print the prefixes
def prefix(string1, alphabet1, alphabet2):
    count = 0
    non_empty_string = ""
     
    string2 = list(string1)
     
    # Loop for iterating the length of
    # the string and print the prefixes
    # and the count of query prefixes.
    for i in range(0, len(string2)):
        non_empty_string = non_empty_string + (string2[i])
         
        if (non_empty_string.count(alphabet1) >
            non_empty_string.count(alphabet2)):
                 
            # prints all required prefixes
            print(non_empty_string)
             
            # increment count
            count += 1
             
    # returns count of the
    # required prefixes
    return(count)
     
# Driver Code
print(prefix("geeksforgeeks", "e", "g"))
 






                        










Output


gee
geek
geeks
geeksf
geeksfo
geeksfor
geeksforge
geeksforgee
geeksforgeek
geeksforgeeks
10




Complexity Analysis:


    

  • Time Complexity: O(N), where N is the length of the string.
    • 

  • Auxiliary Space: O(N)
    • 



Another approach that could be taken is to use a dictionary to store the frequencies of each character in the prefixes as they are generated. This way, rather than iterating through the prefix and counting the occurrences of the two characters every time, you can simply retrieve their frequencies from the dictionary. This can potentially improve the performance of the prefix function, especially for longer strings.


Here is an example of how this approach could be implemented:




Python3














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















def prefix(string1, alphabet1, alphabet2):


    count = 0


    non_empty_string = ""


    prefix_freqs = {}


      


    string2 = list(string1)


      


    # Loop for iterating the length of


    # the string and print the prefixes


    # and the count of query prefixes.


    for i in range(0, len(string2)):


        non_empty_string = non_empty_string + (string2[i])


        prefix_freqs[non_empty_string] = {}


        prefix_freqs[non_empty_string][alphabet1] = non_empty_string.count(alphabet1)


        prefix_freqs[non_empty_string][alphabet2] = non_empty_string.count(alphabet2)


          


        if (prefix_freqs[non_empty_string][alphabet1] > prefix_freqs[non_empty_string][alphabet2]):


            # prints all required prefixes


            print(non_empty_string)


              


            # increment count


            count += 1


              


    # returns count of the


    # required prefixes


    return(count)


   


# Driver Code


print(prefix("geeksforgeeks", "e", "g"))



















                        







                        










Output


gee
geek
geeks
geeksf
geeksfo
geeksfor
geeksforge
geeksforgee
geeksforgeek
geeksforgeeks
10




In the case of the prefix function, the time complexity is O(N), where N is the length of the string. This is because the function loops through the string once and performs a constant amount of work for each character in the string.


In the case of the prefix function, the auxiliary space used is O(N), where N is the length of the string. This is because the function stores the frequencies of all prefixes in a dictionary, and the size of the dictionary is directly proportional to the length of the string.


Using operator.countOf() method




Python3














                                    




                                    

                                    




                                    




                                    

                                    

                                    
                                




















import operator as op


def prefix(string1, alphabet1, alphabet2):


    count = 0


    non_empty_string = ""


    prefix_freqs = {}


      


    string2 = list(string1)


      


    # Loop for iterating the length of


    # the string and print the prefixes


    # and the count of query prefixes.


    for i in range(0, len(string2)):


        non_empty_string = non_empty_string + (string2[i])


        prefix_freqs[non_empty_string] = {}


        prefix_freqs[non_empty_string][alphabet1] = op.countOf(non_empty_string,alphabet1)


        prefix_freqs[non_empty_string][alphabet2] = op.countOf(non_empty_string,alphabet2)


          


        if (prefix_freqs[non_empty_string][alphabet1] > prefix_freqs[non_empty_string][alphabet2]):


            # prints all required prefixes


            print(non_empty_string)


              


            # increment count


            count += 1


              


    # returns count of the


    # required prefixes


    return(count)


   


# Driver Code


print(prefix("geeksforgeeks", "e", "g"))



















                        







                        










Output


gee
geek
geeks
geeksf
geeksfo
geeksfor
geeksforge
geeksforgee
geeksforgeek
geeksforgeeks
10




Time Complexity: O(N), 
Auxiliary Space: O(N)




                                    


                                                                        

                                        

                                            

                                                

                                                    
S

        

            
        

        

                                                

                                                

                                                    Shubham_Singh_29                                                

                                            

                                            

            
                                        

                                        

                                            
    

        
        
    
                                            

                                                
                                                
                                            

                                            

                                            Improve
                                                
                                            

                                        

                                    



                            

                            
 
                                

                                    
                                        Next Article
                                        
                                    
                                    
                                    

                                        Python - Prefix frequency in string List
                                    

                                

                                                        

                            

            

                

                    

                    
                
 
                
    
                            

                                

                            


                            


            

        
  
                        

                                                

                        
                                                    

                                
Similar Reads

                                

                                    
        
            

                
Minimum count of prefixes and suffixes of a string required to form given string

                
Given two strings str1 and str2, the task is to find the minimum number of prefixes and suffixes of str2 required to form the string str1. If the task is not possible, return "-1". Example: Input: str1 = "HELLOWORLD", str2 = "OWORLDHELL"Output: 2Explanation: The above string can be formed as "HELL" + "OWORLD" which are suffix and prefix of the stri

            

            
            

                
                10 min read
            

        
    
        
            

                
Count all prefixes of the given binary array which are divisible by x

                
Given a binary array arr[] and an integer x, the task is to count all the prefixes of the given array which are divisible by x. Note: The ith prefix from arr[0] to arr[i] is interpreted as a binary number (from most-significant-bit to least-significant-bit.)Examples: Input: arr[] = {0, 1, 0, 1, 1}, x = 5 Output: 2 0 = 0 01 = 1 010 = 2 0101 = 5 0101

            

            
            

                
                10 min read
            

        
    
        
            

                
Length of all prefixes that are also the suffixes of given string

                
Given a string S consisting of N characters, the task is to find the length of all prefixes of the given string S that are also suffixes of the same string S. Examples: Input: S = "ababababab"Output: 2 4 6 8Explanation: The prefixes of S that are also its suffixes are: "ab" of length = 2"abab" of length = 4"ababab" of length = 6"abababab" of length

            

            
            

                
                10 min read
            

        
    
        
            

                
Sum of all prefixes of given numeric string

                
Given string str having N characters representing an integer, the task is to calculate the sum of all possible prefixes of the given string. Example: Input: str = "1225"Output: 1360Explanation: The prefixes of the given string are 1, 12, 122, and 1225 and their sum will be 1 + 12 + 122 + 1225 = 1360. Input: str = "20"Output: 22 Approach: The given

            

            
            

                
                8 min read
            

        
    
        
            

                
Find Strings formed by replacing prefixes of given String with given characters

                
Given a String ( S ) of length N and with that String, we need to print a triangle out of it. The triangle should start with the given string and keeps shrinking downwards by removing one character from the beginning of the string. The spaces on the left side of the triangle should be replaced with dot characters ( '.' ). Examples: Input: S = "Geek

            

            
            

                
                9 min read
            

        
    
        
            

                
Check if all prefixes of a number is divisible by remaining count of digits

                
Given a number N, the task is to check if for every value of i (0 <= i <= len), the first i digits of a number is divisible by (len - i + 1) or not, where len is the number of digits in N. If found to be true, then print "Yes". Otherwise, print "No". Examples: Input: N = 52248.Output: YesExplanation: 5 is divisible by 552 is divisible by 4522

            

            
            

                
                4 min read
            

        
    
        
            

                
Count of N digit numbers not having given prefixes

                
Given an integer N and a vector of strings prefixes[], the task is to calculate the total possible strings of length N from characters '0' to '9'. such that the given prefixes cannot be used in any of the strings. Examples: Input: N = 3, prefixes = {"42"}Output: 990Explanation: All string except{"420", "421", "422", "423", "424", "425", "426", "427

            

            
            

                
                8 min read
            

        
    
        
            

                
Count of Strings of Array having given prefixes for Q query

                
Given two arrays of strings containing words[] and queries[] having N and Q strings respectively, the task is to find the number of strings from words[] having queries[i] as the prefix for all the strings in queries[]. Examples: Input: words[] = { "geeks", "geeks", "geeks for geeks", "string", "strong" }, queries[] = { "geek", "gel", "str" }Output:

            

            
            

                
                13 min read
            

        
    
        
            

                
Shift all prefixes by given lengths

                
Given a string S containing letters and digits, and an integer array Shift where, [Tex]1 \leq S.length()=length(Shift) \leq 10^{5} [/Tex]and for each element of Shift array [Tex]0 \leq Shift[i] \leq 10^{9} [/Tex]. The task is, for each Shift[i] = X, you have to shift the first i+1 letters of S, X times. Return the final string after all applying al

            

            
            

                
                6 min read
            

        
    
        
            

                
Find the final String by incrementing prefixes of given length

                
Given a string S and an array roll[] where roll[i] represents incrementing first roll[i] characters in the string, the task is to increment all the prefixes mentioned in the array and find the final string. Note: Incrementing means increasing the ASCII value of the character, like incrementing ‘z’ would result in ‘a', incrementing ‘b’ would result

            

            
            

                
                7 min read
            

        
                                    

                                                                    
                                                            

                        

                        

                                                            

                                    
Article Tags : 

                                    
                                                                    

                                                                                        

                                    
Practice Tags : 

                                    
                                                                    

                                                    

                                                

                                

                                    
                                                                    

                            


                        

                            

                                                                                    

                              

                            

                                                        
                        

                    

                

            

        
        


        

                




	
three90RightbarBannerImg

	
	

	
	

	
	    

	
	

	
	



                
        

    

    

        

            

            

        

    















	

    
  

  
  








    
        We use cookies to ensure you have the best browsing experience on our website. By using our site, you
        acknowledge that you have read and understood our
        Cookie Policy &
        Privacy Policy
            
    







   Lightbox