पायथन प्रोग्राम: स्ट्रीम से पहला नॉन-रिपीटिंग कैरेक्टर ढूंढें

स्ट्रिंग या कैरेक्टर स्ट्रीम से पहला अद्वितीय (नॉन-रिपीटिंग) वर्ण ढूंढना एक सामान्य साक्षात्कार प्रश्न है।

विधि 1: काउंटर + ऑर्डर संरक्षण (O(n))

def first_non_repeating_char(s):
    """
    पहला नॉन-रिपीटिंग कैरेक्टर लौटाता है, यदि कोई नहीं तो None।
    समय: O(n), स्थान: O(k) जहां k = अद्वितीय वर्ण
    """
    char_order = []      # वर्णों का क्रम बनाए रखें
    counts = {}          # फ्रीक्वेंसी काउंट
    
    for c in s:
        if c in counts:
            counts[c] += 1
        else:
            counts[c] = 1
            char_order.append(c)
    
    # क्रम में पहला वर्ण ढूंढें जिसकी काउंट 1 हो
    for c in char_order:
        if counts[c] == 1:
            return c
    
    return None

# टेस्ट
print(first_non_repeating_char('PythonforallPythonMustforall'))  # M
print(first_non_repeating_char('tutorialspointfordeveloper'))    # u
print(first_non_repeating_char('AABBCC'))                         # None

आउटपुट

M
u
None

विधि 2: collections.OrderedDict (पायथन 3.7+ में dict क्रमबद्ध है)

from collections import OrderedDict

def first_non_repeating_ordereddict(s):
    counts = OrderedDict()
    
    for c in s:
        counts[c] = counts.get(c, 0) + 1
    
    for char, count in counts.items():
        if count == 1:
            return char
    return None

विधि 3: collections.Counter (संक्षिप्त)

from collections import Counter

def first_non_repeating_counter(s):
    counts = Counter(s)
    for c in s:
        if counts[c] == 1:
            return c
    return None

विधि 4: व्हाइल लूप दृष्टिकोण (मूल लेख)

def first_non_repeating_while(s):
    while s != "":
        slen0 = len(s)
        ch = s[0]
        s = s.replace(ch, "")  # सभी occurrences हटाएं
        slen1 = len(s)
        
        if slen1 == slen0 - 1:
            # केवल एक occurrence था
            return ch
    return None

print(first_non_repeating_while("tutorialspointfordeveloper"))  # u

नोट: विधि 4 O(n²) है क्योंकि प्रत्येक replace O(n) है। बड़े स्ट्रिंग्स के लिए विधि 1 या 3 उपयोग करें।

स्ट्रीमिंग संस्करण (ऑनलाइन एल्गोरिदम)

यदि वर्ण एक-एक करके आ रहे हों (स्ट्रीम):

from collections import deque, defaultdict

class FirstNonRepeatingStream:
    def __init__(self):
        self.counts = defaultdict(int)
        self.queue = deque()  # संभावित उम्मीदवार
    
    def add(self, char):
        """नया वर्ण जोड़ें"""
        self.counts[char] += 1
        if self.counts[char] == 1:
            self.queue.append(char)
        # कतार के सामने से रिपीटिंग वर्ण हटाएं
        while self.queue and self.counts[self.queue[0]] > 1:
            self.queue.popleft()
    
    def get_first_non_repeating(self):
        """वर्तमान पहला नॉन-रिपीटिंग वर्ण"""
        return self.queue[0] if self.queue else None

# उपयोग
stream = FirstNonRepeatingStream()
for ch in "tutorialspointfordeveloper":
    stream.add(ch)
    print(f"'{ch}' जोड़ने के बाद: पहला नॉन-रिपीटिंग = {stream.get_first_non_repeating()}")

आउटपुट (आंशिक)

't' जोड़ने के बाद: पहला नॉन-रिपीटिंग = t
'u' जोड़ने के बाद: पहला नॉन-रिपीटिंग = t
't' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'o' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'r' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'i' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'a' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'l' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
's' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'p' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'o' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'i' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'n' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
't' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'f' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'o' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'r' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'd' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'e' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'v' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'e' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'l' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'o' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'p' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'e' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u
'r' जोड़ने के बाद: पहला नॉन-रिपीटिंग = u

समय/स्थान जटिलता तुलना

एक्सटेंशन: पहला नॉन-रिपीटिंग वर्ड

def first_non_repeating_word(text):
    words = text.split()
    counts = Counter(words)
    for w in words:
        if counts[w] == 1:
            return w
    return None

print(first_non_repeating_word("the quick brown fox jumps over the lazy dog"))
# quick