logo

TechCodeview

K'th icke-upprepande karaktär

Med en sträng strö av längd n (1<= n <= 106) och ett nummer k Uppgiften är att hitta KTH icke-upprepande karaktär i strängen.

java index för

Exempel:  



Input: str = GeeksForgeeks K = 3
Output: r
Förklaring: Första icke-upprepande karaktären är f Second Is o och tredje är r.

Input: str = geeksForgeeks k = 2
Output: de

binärt sökträd]

Input : str = geeksorgeeks k = 4
Output: Mindre än K-icke-upprepande tecken i input.



Detta problem är främst en förlängning av Första icke-upprepande karaktärsproblem .

K'th icke-upprepande karaktär med kapslad slinga:

En enkel lösning är att köra två slingor. Börja korsa från vänster sida. För varje karaktär, kontrollera om den upprepar eller inte. Om karaktären inte upprepar ökningen av räkningen av icke-upprepande karaktärer. När CO i nt blir k returnera karaktären.

Nedan är implementeringen av ovanstående idé:



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

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

Tidskomplexitet: O (n²)
Hjälp- Utrymme: O (1)

java polymorfism

K'th icke-upprepande karaktär med Hashing :

  • Skapa en tom hashkarta för att lagra karaktär räkning .
  • Slinga genom strängen och uppdatera räkningarna för varje tecken på hash -kartan.
  • Loop genom strängen igen och hitta KTH icke-upprepande karaktär genom att kontrollera räkningen för varje tecken på hash-kartan.

Nedan är implementeringen av ovanstående idé:

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

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

Tidskomplexitet: O (n)
Hjälputrymme: O (n)