K번째 비반복 문자
문자열이 주어지면 str 길이 n (1 <= n <= 10 6 ) 및 숫자 케이 작업은 문자열에서 반복되지 않는 k번째 문자를 찾는 것입니다.
예:
입력 : str = 긱스포긱스 k = 3
출력 : 아르 자형
설명: 반복되지 않는 첫 번째 문자는 f, 두 번째는 o, 세 번째는 r입니다.입력 : str = 긱스포긱스 k = 2
출력 : 그만큼입력 : str = geeksforgeeks k = 4
출력 : 입력에 k개 미만의 반복되지 않는 문자가 있습니다.
이 문제는 주로 다음의 확장입니다. 첫 번째 반복되지 않는 문자 문제 .
중첩 루프를 사용하는 K번째 비반복 문자:
간단한 해결책은 두 개의 루프를 실행하는 것입니다. 왼쪽부터 횡단을 시작합니다. 모든 문자에 대해 반복되는지 여부를 확인하세요. 문자가 반복되지 않으면 반복되지 않는 문자의 개수를 늘립니다. 공동 때 ~에 nt는된다 케이 문자를 반환합니다.
다음은 위의 아이디어를 구현한 것입니다.
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 } ` ); }
산출
The 3th non-repeating character in the string is r.
시간 복잡도: 오(n²)
보조자 공간: 오(1)
K번째 비반복 문자 사용 해싱 :
- 캐릭터를 저장할 빈 해시 맵을 만듭니다. 카운트 .
- 문자열을 반복하고 해시 맵의 각 문자 수를 업데이트합니다.
- 문자열을 다시 반복하고 해시 맵의 각 문자 수를 확인하여 k번째 반복되지 않는 문자를 찾습니다.
다음은 위의 아이디어를 구현한 것입니다.
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 ();
산출
The 3th non-repeating character in the string is r.
시간 복잡도: 에)
보조 공간: 에)
