K’th Non-repeating Character in Python using List Comprehension and OrderedDict

Last Updated : 21 Jul, 2022

Given a string and a number k, find the k-th non-repeating character in the string. Consider a large input string with lacs of characters and a small character set. How to find the character by only doing only one traversal of input string? Examples:

Input : str = geeksforgeeks, k = 3
Output : r
First non-repeating character is f,
second is o and third is r.

Input : str = geeksforgeeks, k = 2
Output : o

Input : str = geeksforgeeks, k = 4
Output : Less than k non-repeating
         characters in input.

This problem has existing solution please refer link. We can solve this problem quickly in python using List Comprehension and OrderedDict.

Implementation:

Python3

# Function to find k'th non repeating character
# in string
from collections import OrderedDict
 
def kthRepeating(input,k):
 
    # OrderedDict returns a dictionary data
        # structure having characters of input
    # string as keys in the same order they
        # were inserted and 0 as their default value
    dict=OrderedDict.fromkeys(input,0)
 
    # now traverse input string to calculate
        # frequency of each character
    for ch in input:
        dict[ch]+=1
 
    # now extract list of all keys whose value
        # is 1 from dict Ordered Dictionary
    nonRepeatDict = [key for (key,value) in dict.items() if value==1]
     
    # now return (k-1)th character from above list
    if len(nonRepeatDict) < k:
        return 'Less than k non-repeating characters in input.'
    else:
        return nonRepeatDict[k-1]
 
# Driver function
if __name__ == "__main__":
    input = "geeksforgeeks"
    k = 3
    print (kthRepeating(input, k))

Output

GeeksforGeeks

Improve

Python | Check order of character in string using OrderedDict( )

Similar Reads

Python | Check order of character in string using OrderedDict( )

Given an input string and a pattern, check if characters in the input string follows the same order as determined by characters present in the pattern. Assume there won’t be any duplicate characters in the pattern. Examples: Input: string = "engineers rock"pattern = "er";Output: trueExplanation: All 'e' in the input string are before all 'r'.Input:

Find the two non-repeating elements in an array of repeating elements/ Unique Numbers 2

Given an array arr[] containing 2*N+2 positive numbers, out of which 2*N numbers exist in pairs whereas the other two number occur exactly once and are distinct. Find the other two numbers. Return in increasing order. Example: Input: N = 2, arr[] = {1, 2, 3, 2, 1, 4}Output:3 4 Explanation: 3 and 4 occur exactly once. Input: N = 1, arr[] = {2, 1, 3,

Find first non-repeating character in a given string using Linked List

Given a string str of length L, the task is to find the first occurrence of a non-repeating character in the string. Examples: Input: str = "geeksforgeeks"Output: f Input: str = "programmer"Output: p Note: Please refer this article for HashMap approach and this article as space-optimized approach. Linked List Approach: The idea is to use Linked Lis

LRU Cache in Python using OrderedDict

LRU (Least Recently Used) Cache discards the least recently used items first. This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping "age bits" for cache-lines and track the "Least

First non-repeating character using one traversal of string | Set 2

Given a string, find the first non-repeating character in it. For example, if the input string is "GeeksforGeeks", then output should be 'f' and if input string is "GeeksQuiz", then output should be 'G'. Recommended: Please solve it on “PRACTICE ” first, before moving on to the solution. We have discussed two solutions in Given a string, find its f

Python - Insertion at the beginning in OrderedDict

Given an ordered dict, write a program to insert items in the beginning of the ordered dict. Examples: Input: original_dict = {'a':1, 'b':2} item to be inserted ('c', 3) Output: {'c':3, 'a':1, 'b':2}Input: original_dict = {'akshat':1, 'manjeet':2} item to be inserted ('nikhil', 3) Output: {'nikhil':3, 'akshat':1, 'manjeet':2} Below are various meth

How to iterate over OrderedDict in Python?

An OrderedDict is a subclass that preserves the order in which the keys are inserted. The difference between OrderedDict and Dict is that the normal Dict does not keep a track of the way the elements are inserted whereas the OrderedDict remembers the order in which the elements are inserted. Explanation: Input : original_dict = { 'a':1, 'b':2, 'c':

OrderedDict in Python

An OrderedDict is a dictionary subclass that remembers the order in which keys were first inserted. The only difference between dict() and OrderedDict() lies in their handling of key order in Python. OrderedDict vs dict in Python`OrderedDict` maintains the sequence in which keys are added, ensuring that the order is preserved during iteration. In c

Find the last non repeating character in string

Given a string str, the task is to find the last non-repeating character in it. For example, if the input string is "GeeksForGeeks", then the output should be 'r' and if the input string is "GeeksQuiz" then the output should be 'z'. if there is no non-repeating character then print -1.Examples: Input: str = "GeeksForGeeks" Output: r 'r' is the firs

Queries to find the last non-repeating character in the sub-string of a given string

Given a string str, the task is to answer Q queries where every query consists of two integers L and R and we have to find the last non-repeating character in the sub-string str[L...R]. If there is no non-repeating character then print -1.Examples: Input: str = "GeeksForGeeks", q[] = {{2, 9}, {2, 3}, {0, 12}} Output: G k r Sub-string for the querie

Article Tags :

Practice Tags :