How to Find the K’th Non-Repeating Character in Python Using List Comprehension and OrderedDict

How to Find the K’th Non-Repeating Character in Python Using List Comprehension and OrderedDict

When working with strings, a common problem is finding non-repeating characters. In this tutorial, we’ll show you how to find the K’th non-repeating character in a string using Python. We’ll use list comprehension for concise code and OrderedDict from the collections module to maintain character order and frequency.

Steps to Solve the Problem

1. Understanding the Problem: We are given a string, and we need to find the K’th non-repeating character, i.e., the character that appears exactly once and is the K’th such character in the order it first appeared.
2. Approach:
   • OrderedDict will allow us to maintain the order of insertion while counting occurrences of each character.
   • List Comprehension will help us quickly extract characters that appear only once.

Solution Breakdown

Step 1: Import Necessary Modules

from collections import OrderedDict

We import OrderedDict from the collections module because it keeps track of the order in which characters are added.

Step 2: Function to Find the K’th Non-Repeating Character

def find_kth_non_repeating_char(string, k):
    # Create an ordered dictionary to store the count of each character
    char_count = OrderedDict()
    
    # Count the frequency of each character
    for char in string:
        char_count[char] = char_count.get(char, 0) + 1

    # Use list comprehension to collect all non-repeating characters
    non_repeating_chars = [char for char, count in char_count.items() if count == 1]

    # Check if k is within the bounds of the list of non-repeating characters
    if k <= len(non_repeating_chars):
        return non_repeating_chars[k-1]  # k-1 for 0-based index
    else:
        return None  # If k is out of bounds

Step 3: Explanation of the Code

• OrderedDict Initialization: We create an empty OrderedDict called char_count. As we loop through the string, the dictionary will store each character as the key and its frequency as the value.
• Counting Characters: In the loop for char in string, we use the get() method to either update the count of an existing character or set it to 1 if it's seen for the first time.
• List Comprehension: This line uses list comprehension to build a list of characters that appear only once.
• Check the Value of k: After extracting the non-repeating characters, we check if k is less than or equal to the length of the non_repeating_chars list. If so, we return the K'th character (adjusted for zero-based indexing), otherwise, return None.

Step 4: Testing the Function

# Test cases
print(find_kth_non_repeating_char("geeksforgeeks", 2))  # Output: 'r'
print(find_kth_non_repeating_char("abcabc", 1))         # Output: None (no non-repeating characters)
print(find_kth_non_repeating_char("swiss", 1))          # Output: 'w'

Conclusion

By using Python’s OrderedDict and list comprehension, we can efficiently find the K'th non-repeating character in a string while preserving the order of characters. This approach is both concise and readable, leveraging Python’s powerful built-in features.

Feel free to adapt the solution to your specific needs or improve upon it for more complex scenarios!