K'th nekonservuojantis personažas
Duota eilutė str ilgio n (1 <= n <= 10 6 ) ir skaičius k Užduotis yra rasti KTH nekartojantį simbolią eilutėje.
Pavyzdžiai:
Įvestis: str = geeksforgeeks k = 3
Išvestis: r
Paaiškinimas: Pirmasis nekartojantis pobūdis yra f antrasis yra o, o trečiasis-r.Įvestis: str = geeksforgeeks k = 2
Išvestis:Įvestis : str = geeksforgeeks k = 4
Išvestis: Mažiau nei K nekartojančių simbolių įvestyje.
Ši problema daugiausia yra Pirmoji nekartojanti charakterio problema .
K'th nekonservuojantis personažas, naudojant įdėtą kilpą:
Paprastas sprendimas yra paleisti dvi kilpas. Pradėkite važiuoti iš kairės pusės. Kiekvienam simboliui patikrinkite, ar jis kartojasi, ar ne. Jei simbolis nekartoja padidinti nesikartojančių simbolių skaičiaus. Kai co į nt tampa k grąžinti personažą.
Žemiau pateikiama aukščiau pateiktos idėjos įgyvendinimas:
C++ // Include all standard libraries #include using namespace std ; // Define a function to find the kth non-repeating character // in a string char kthNonRepeatingChar ( string str int k ) { // Initialize count and result variables to 0 and null // character respectively int count = 0 ; char result = ' ' ; // Loop through each character in the string for ( int i = 0 ; i < str . length (); i ++ ) { // Assume that the current character does not repeat bool repeating = false ; // Loop through the rest of the string to check if // the current character repeats for ( int j = 0 ; j < i ; j ++ ) { if ( str [ j ] == str [ i ]) { repeating = true ; } } for ( int j = i + 1 ; j < str . length (); j ++ ) { if ( str [ i ] == str [ j ]) { // If the current character repeats set the // repeating flag to true and exit the loop repeating = true ; } } // If the current character does not repeat // increment the count of non-repeating characters if ( ! repeating ) { count ++ ; // If the count of non-repeating characters // equals k set the result variable to the // current character and exit the loop if ( count == k ) { result = str [ i ]; break ; } } } // Return the result variable return result ; } // Define the main function to test the kthNonRepeatingChar // function int main () { // Define an example string and value of k string str = 'geeksforgeeks' ; int k = 3 ; // Call the kthNonRepeatingChar function with the // example string and value of k char result = kthNonRepeatingChar ( str k ); // Check if the result variable contains a non-null // character and print the appropriate message if ( result == ' ' ) { cout < < 'There is no kth non-repeating character ' 'in the string. n ' ; } else { cout < < 'The ' < < k < < 'th non-repeating character in the string ' 'is ' < < result < < '. n ' ; } // End the program return 0 ; }
Java // Import required libraries import java.util.* ; // Define a class to find the kth non-repeating character // in a string public class Main { public static char kthNonRepeatingChar ( String str int k ) { // Initialize count and result variables to 0 and // null character respectively int count = 0 ; char result = ' ' ; // Loop through each character in the string for ( int i = 0 ; i < str . length (); i ++ ) { // Assume that the current character does not // repeat boolean repeating = false ; // Loop through the rest of the string to check // if the current character repeats for ( int j = i + 1 ; j < str . length (); j ++ ) { if ( str . charAt ( i ) == str . charAt ( j )) { // If the current character repeats set // the repeating flag to true and exit // the loop repeating = true ; break ; } } // If the current character does not repeat // increment the count of non-repeating // characters if ( ! repeating ) { count ++ ; // If the count of non-repeating characters // equals k set the result variable to the // current character and exit the loop if ( count == k ) { result = str . charAt ( i ); break ; } } } // Return the result variable return result ; } // Define the main function to test the // kthNonRepeatingChar function public static void main ( String [] args ) { // Define an example string and value of k String str = 'geeksforgeeks' ; int k = 3 ; // Call the kthNonRepeatingChar function with the // example string and value of k char result = kthNonRepeatingChar ( str k ); // Check if the result variable contains a non-null // character and print the appropriate message if ( result == ' ' ) { System . out . println ( 'There is no kth non-repeating character ' + 'in the string.' ); } else { System . out . println ( 'The ' + k + 'th non-repeating character in the string ' + 'is ' + result + '.' ); } } }
Python # Define a function to find the kth non-repeating character # in a string def kthNonRepeatingChar ( s : str k : int ) -> str : # Initialize count and result variables to 0 and null # character respectively count = 0 result = ' ' # Loop through each character in the string for i in range ( len ( s )): # Assume that the current character does not repeat repeating = False # Loop through the rest of the string to check if # the current character repeats for j in range ( i + 1 len ( s )): if s [ i ] == s [ j ]: # If the current character repeats set the # repeating flag to true and exit the loop repeating = True break # If the current character does not repeat # increment the count of non-repeating characters if not repeating : count += 1 # If the count of non-repeating characters # equals k set the result variable to the # current character and exit the loop if count == k : result = s [ i ] break # Return the result variable return result # Define the main function to test the kthNonRepeatingChar # function if __name__ == '__main__' : # Define an example string and value of k s = 'geeksforgeeks' k = 3 # Call the kthNonRepeatingChar function with the # example string and value of k result = kthNonRepeatingChar ( s k ) # Check if the result variable contains a non-null # character and print the appropriate message if result == ' ' : print ( 'There is no kth non-repeating character ' 'in the string.' ) else : print ( f 'The { k } th non-repeating character in the string ' f 'is { result } .' ) # This code is contributed by Susobhan Akhuli
C# using System ; public class Program { // Define a function to find the kth non-repeating // character in a string static char kthNonRepeatingChar ( string str int k ) { // Initialize count and result variables to 0 and // null character respectively int count = 0 ; char result = ' ' ; // Loop through each character in the string for ( int i = 0 ; i < str . Length ; i ++ ) { // Assume that the current character does not // repeat bool repeating = false ; // Loop through the rest of the string to check // if the current character repeats for ( int j = i + 1 ; j < str . Length ; j ++ ) { if ( str [ i ] == str [ j ]) { // If the current character repeats set // the repeating flag to true and exit // the loop repeating = true ; break ; } } // If the current character does not repeat // increment the count of non-repeating // characters if ( ! repeating ) { count ++ ; // If the count of non-repeating characters // equals k set the result variable to the // current character and exit the loop if ( count == k ) { result = str [ i ]; break ; } } } // Return the result variable return result ; } // Define the main function to test the // kthNonRepeatingChar function static void Main ( string [] args ) { // Define an example string and value of k string str = 'geeksforgeeks' ; int k = 3 ; // Call the kthNonRepeatingChar function with the // example string and value of k char result = kthNonRepeatingChar ( str k ); // Check if the result variable contains a non-null // character and print the appropriate message if ( result == ' ' ) { Console . WriteLine ( 'There is no kth non-repeating character ' + 'in the string.' ); } else { Console . WriteLine ( 'The ' + k + 'th non-repeating character in the string is ' + result + '.' ); } } } // This code is contributed by Susobhan Akhuli
JavaScript // Define a function to find the kth non-repeating character // in a string function kthNonRepeatingChar ( str k ) { // Initialize count and result variables to 0 and null // character respectively let count = 0 ; let result = ' ' ; // Loop through each character in the string for ( let i = 0 ; i < str . length ; i ++ ) { // Assume that the current character does not repeat let repeating = false ; // Loop through the rest of the string to check if // the current character repeats for ( let j = i + 1 ; j < str . length ; j ++ ) { if ( str [ i ] == str [ j ]) { // If the current character repeats set the // repeating flag to true and exit the loop repeating = true ; break ; } } // If the current character does not repeat // increment the count of non-repeating characters if ( ! repeating ) { count ++ ; // If the count of non-repeating characters // equals k set the result variable to the // current character and exit the loop if ( count == k ) { result = str [ i ]; break ; } } } // Return the result variable return result ; } // Define the main function to test the kthNonRepeatingChar // function // Define an example string and value of k let str = 'geeksforgeeks' ; let k = 3 ; // Call the kthNonRepeatingChar function with the // example string and value of k let result = kthNonRepeatingChar ( str k ); // Check if the result variable contains a non-null // character and print the appropriate message if ( result == ' ' ) { console . log ( 'There is no kth non-repeating character in the string.' ); } else { console . log ( `The ${ k } th non-repeating character in the string is ${ result } ` ); }
Išvestis
The 3th non-repeating character in the string is r.
Laiko sudėtingumas: O (n²)
Pagalbinis Erdvė: O (1)
K'th nekonsultuojantis personažas naudojant Maiša :
- Sukurkite tuščią maišos žemėlapį, kad galėtumėte laikyti personažą skaičiuoja .
- Perbraukite per eilutę ir atnaujinkite kiekvieno simbolio skaičiavimą maišos žemėlapyje.
- Vėl kilite per stygą ir suraskite KTH nekartojantį personažą, patikrindami kiekvieno simbolio skaičiavimą maišos žemėlapyje.
Žemiau pateikiama aukščiau pateiktos idėjos įgyvendinimas:
C++ #include using namespace std ; char kthNonRepeatingChar ( string str int k ) { // Create an empty hash map to store the counts of each // character in the string unordered_map < char int > charCounts ; // Loop through the string and store the counts of each // character in the hash map for ( int i = 0 ; i < str . length (); i ++ ) { charCounts [ str [ i ]] ++ ; } // Loop through the string and find the kth // non-repeating character int nonRepeatingCount = 0 ; for ( int i = 0 ; i < str . length (); i ++ ) { if ( charCounts [ str [ i ]] == 1 ) { nonRepeatingCount ++ ; if ( nonRepeatingCount == k ) { // When the count of non-repeating // characters equals k return the character return str [ i ]; } } } // If there is no kth non-repeating character in the // string return the null character return ' ' ; } int main () { string str = 'geeksforgeeks' ; int k = 3 ; char result = kthNonRepeatingChar ( str k ); if ( result == ' ' ) { cout < < 'There is no kth non-repeating character ' 'in the string. n ' ; } else { cout < < 'The ' < < k < < 'th non-repeating character in the string ' 'is ' < < result < < '. n ' ; } return 0 ; }
Java import java.util.* ; public class Main { public static char kthNonRepeatingChar ( String str int k ) { // Create an empty hash map to store the counts of each // character in the string Map < Character Integer > charCounts = new HashMap <> (); // Loop through the string and store the counts of each // character in the hash map for ( int i = 0 ; i < str . length (); i ++ ) { char c = str . charAt ( i ); charCounts . put ( c charCounts . getOrDefault ( c 0 ) + 1 ); } // Loop through the string and find the kth // non-repeating character int nonRepeatingCount = 0 ; for ( int i = 0 ; i < str . length (); i ++ ) { char c = str . charAt ( i ); if ( charCounts . get ( c ) == 1 ) { nonRepeatingCount ++ ; if ( nonRepeatingCount == k ) { // When the count of non-repeating // characters equals k return the character return c ; } } } // If there is no kth non-repeating character in the // string return the null character return ' ' ; } public static void main ( String [] args ) { String str = 'geeksforgeeks' ; int k = 3 ; char result = kthNonRepeatingChar ( str k ); if ( result == ' ' ) { System . out . println ( 'There is no kth non-repeating character ' + 'in the string.' ); } else { System . out . println ( 'The ' + k + 'th non-repeating character ' + 'in the string is ' + result + '.' ); } } }
Python # Python code of the above approach def kth_non_repeating_char ( string k ): # Create an empty dictionary to store # the counts of each character in the string char_counts = {} # Loop through the string and store # the counts of each character in the dictionary for char in string : if char in char_counts : char_counts [ char ] += 1 else : char_counts [ char ] = 1 # Loop through the string and find the kth non-repeating character non_repeating_count = 0 for char in string : if char_counts [ char ] == 1 : non_repeating_count += 1 if non_repeating_count == k : # When the count of non-repeating # characters equals k return the character return char # If there is no kth non-repeating character in the string return None return None # Main function if __name__ == '__main__' : string = 'geeksforgeeks' k = 3 result = kth_non_repeating_char ( string k ) if result is None : print ( 'There is no kth non-repeating character in the string.' ) else : print ( f 'The { k } th non-repeating character in the string is { result } .' ) # This code is contributed by Susobhan Akhuli
C# using System ; using System.Collections.Generic ; class Gfg { static char kthNonRepeatingChar ( string str int k ) { // Create a dictionary to store the counts of each character in the string Dictionary < char int > charCounts = new Dictionary < char int > (); // Loop through the string and store // the counts of each character in the dictionary foreach ( char c in str ) { if ( charCounts . ContainsKey ( c )) { charCounts [ c ] ++ ; } else { charCounts [ c ] = 1 ; } } // Loop through the string and find // the kth non-repeating character int nonRepeatingCount = 0 ; foreach ( char c in str ) { if ( charCounts [ c ] == 1 ) { nonRepeatingCount ++ ; if ( nonRepeatingCount == k ) { // When the count of non-repeating characters equals k return the character return c ; } } } // If there is no kth non-repeating character in the string return the null character return ' ' ; } static void Main () { string str = 'geeksforgeeks' ; int k = 3 ; char result = kthNonRepeatingChar ( str k ); if ( result == ' ' ) { Console . WriteLine ( 'There is no kth non-repeating character in the string.' ); } else { Console . WriteLine ( $'The {k}th non-repeating character in the string is {result}.' ); } } }
JavaScript function kthNonRepeatingChar ( str k ) { // Create an empty map to store the counts of each // character in the string const charCounts = new Map (); // Loop through the string and store the counts of each // character in the map for ( let i = 0 ; i < str . length ; i ++ ) { const char = str [ i ]; charCounts . set ( char ( charCounts . get ( char ) || 0 ) + 1 ); } // Loop through the string and find the kth non-repeating character let nonRepeatingCount = 0 ; for ( let i = 0 ; i < str . length ; i ++ ) { const char = str [ i ]; if ( charCounts . get ( char ) === 1 ) { nonRepeatingCount ++ ; if ( nonRepeatingCount === k ) { // When the count of non-repeating characters equals k // return the character return char ; } } } // If there is no kth non-repeating character in the string // return the null character return ' ' ; } // Main function function main () { const str = 'geeksforgeeks' ; const k = 3 ; const result = kthNonRepeatingChar ( str k ); if ( result === ' ' ) { console . log ( 'There is no kth non-repeating character in the string.' ); } else { console . log ( `The ${ k } th non-repeating character in the string is ${ result } .` ); } } main ();
Išvestis
The 3th non-repeating character in the string is r.
Laiko sudėtingumas: O (n)
Pagalbinė erdvė: O (n)
