logo

K'th Nicht wiederauflösender Charakter

Bei einer Zeichenfolge str von Länge N (1<= n <= 106) und eine Nummer k Die Aufgabe besteht darin, den nicht wiederholenden KTH-Charakter in der Zeichenfolge zu finden.

Rekha-Alter

Beispiele:  



Eingabe: STR = GeeksForgeeks K = 3
Ausgabe : R
Erläuterung: Der erste nicht wiederauflösende Charakter ist f zweite ist o und der dritte ist r.

Eingabe: STR = GeeksForgeeks K = 2
Ausgabe : Die

wie die Schule erfunden wurde

Eingang : str = geeksforgeeks k = 4
Ausgabe : Weniger als K-nicht wieder aufgenommene Zeichen.



Dieses Problem ist hauptsächlich eine Erweiterung der Erstes nicht wiederauflösendes Charakterproblem .

K'th-nicht wiederholender Charakter mit verschachtelter Schleife:

Eine einfache Lösung besteht darin, zwei Schleifen auszuführen. Beginnen Sie von der linken Seite. Für jeden Charakter überprüfen Sie, ob es sich wiederholt oder nicht. Wenn der Charakter nicht wiederholt, erhöhen Sie die Anzahl der nicht wiederholenden Zeichen. Wenn der co In nt wird k Geben Sie den Charakter zurück.

Nachfolgend finden Sie die Implementierung der obigen Idee:



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}`); } 

Ausgabe
The 3th non-repeating character in the string is r. 

Zeitkomplexität: O (n²)
Hilfs Raum: O (1)

Javascript-Druck

K'th-nicht wiederauflösender Charakter verwenden Hashing :

  • Erstellen Sie eine leere Hash -Karte, um Charakter zu speichern zählt .
  • Schleifen Sie die Zeichenfolge durch und aktualisieren Sie die Zählungen jedes Zeichens in der Hash -Karte.
  • Schleifen Sie erneut durch die Zeichenfolge und finden Sie das nicht wiederholende KTH-Zeichen, indem Sie die Anzahl der einzelnen Zeichen in der Hash-Karte überprüfen.

Nachfolgend finden Sie die Implementierung der obigen Idee:

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(); 

Ausgabe
The 3th non-repeating character in the string is r. 

Zeitkomplexität: An)
Hilfsraum: An)