ഒരു സ്ട്രീമിലെ ആദ്യത്തെ ആവർത്തിക്കാത്ത പ്രതീകത്തിനായുള്ള ക്യൂ അടിസ്ഥാനമാക്കിയുള്ള സമീപനം  


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഫ്ലിപ്പ്കാർട്ട് മൈക്രോസോഫ്റ്റ് പേ യാഹൂ
ഹാഷ് ലിങ്ക്ഡ്-ലിസ്റ്റ് വരി സ്ട്രിംഗ്

പ്രശ്നം പ്രസ്താവന  

“ഒരു സ്ട്രീമിലെ ആദ്യത്തെ ആവർത്തിക്കാത്ത പ്രതീകത്തിനായുള്ള ക്യൂ അടിസ്ഥാനമാക്കിയുള്ള സമീപനം” എന്ന പ്രശ്നം, നിങ്ങൾക്ക് ചെറിയ കേസ് അടങ്ങിയ ഒരു സ്ട്രീം നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു പ്രതീകങ്ങൾ, സ്ട്രീമിലേക്ക് ഒരു പുതിയ പ്രതീകം ചേർക്കുമ്പോഴെല്ലാം ആവർത്തിക്കാത്ത ആദ്യത്തെ പ്രതീകം കണ്ടെത്തുക, കൂടാതെ ആവർത്തിക്കാത്ത പ്രതീക റിട്ടേൺ -1 ഇല്ലെങ്കിൽ.

ഉദാഹരണങ്ങൾ  

aabcddbe
a -1 b b b b c c

വിശദീകരണം: രണ്ടാമത്തെ സൂചിക ഒഴികെ എല്ലായിടത്തും output ട്ട്‌പുട്ടിന് ആദ്യത്തെ ആവർത്തിക്കാത്ത പ്രതീകം ഉണ്ടെന്ന് നമുക്ക് കാണാൻ കഴിയും. സൂചിക 2 വരെ എല്ലാ പ്രതീകങ്ങളും ആവർത്തിച്ചു. അതിനാൽ, -1 സൂചിക 2 ൽ അച്ചടിക്കുന്നു.

abcdabcd
a a a a b c d -1

 

ഒരു സ്ട്രീമിലെ ആദ്യത്തെ ആവർത്തിക്കാത്ത പ്രതീകത്തിനായുള്ള ക്യൂ അടിസ്ഥാനമാക്കിയുള്ള സമീപനം

ഒരു സ്ട്രീമിലെ ആദ്യത്തെ ആവർത്തിക്കാത്ത പ്രതീകത്തിനായുള്ള അൽഗോരിതം  

മുകളിലുള്ള പ്രശ്നം a ഉപയോഗിച്ച് പരിഹരിക്കാൻ കഴിയും ക്യൂ. അതിനാൽ, നമുക്ക് പ്രതീകങ്ങളുടെ ഒരു നിര നിലനിർത്തേണ്ടതുണ്ട്, കൂടാതെ ഒരു ശ്രേണി ആവൃത്തിയുടെ. സ്ട്രീമിലെ എല്ലാ പ്രതീകങ്ങളുടെയും ആവൃത്തി അറേ സംഭരിക്കുന്നു.
അങ്ങനെ സ്ട്രീമിലെ ഓരോ പ്രതീകത്തിനും. എന്നിട്ട് ആ പ്രതീകത്തിന്റെ ആവൃത്തി വർദ്ധിപ്പിച്ച് ക്യൂവിലേക്ക് തള്ളുക. ക്യൂവിന്റെ തുടക്കത്തിൽ പ്രതീകം പരിശോധിക്കുക, ആ പ്രതീകത്തിന്റെ ആവൃത്തി 1 ആണെങ്കിൽ, പ്രതീകം നൽകുക. അല്ലെങ്കിൽ, പ്രതീകം പോപ്പ് out ട്ട് ചെയ്‌ത് അടുത്ത പ്രതീകത്തിനായി പരിശോധിക്കുക. ക്യൂ ശൂന്യമാവുകയാണെങ്കിൽ, -1 മടക്കി സ്ട്രീമിലെ മറ്റ് പ്രതീകങ്ങൾ പ്രോസസ്സ് ചെയ്യുന്നത് തുടരുക.

  1. പ്രതീകങ്ങളുടെ ഒരു നിരയും ഓരോ പ്രതീകത്തിന്റെയും ആവൃത്തി സംഭരിക്കുന്ന ഒരു അറേയും സൃഷ്ടിക്കുക.
  2. ഓരോന്നായി സ്ട്രീമിന്റെ ഇൻപുട്ടുകൾ പ്രോസസ്സ് ചെയ്യുന്നു.
  3. സ്ട്രീമിലെ നിലവിലെ പ്രതീക ഇൻപുട്ടിനായി, ആവൃത്തി വർദ്ധിപ്പിച്ച് ക്യൂവിലേക്ക് നീക്കുക.
  4. ക്യൂവിനു മുന്നിലുള്ള പ്രതീകം പരിശോധിക്കുക, ആ പ്രതീകത്തിന്റെ ആവൃത്തി 1 ആണെങ്കിൽ, പ്രതീകം പ്രിന്റുചെയ്യുക, അല്ലെങ്കിൽ ക്യൂവിലെ ആദ്യ പ്രതീകം നീക്കംചെയ്‌ത് ഘട്ടം 4 ആവർത്തിക്കുക.
  5. നാലാം ഘട്ടത്തിൽ ക്യൂ ശൂന്യമാവുകയാണെങ്കിൽ, -4 പ്രിന്റുചെയ്‌ത് അടുത്ത പ്രതീകം പ്രോസസ്സ് ചെയ്യുന്നത് തുടരുക.
ഇതും കാണുക
വൃത്താകൃതിയിലുള്ള അറേ ഉപയോഗിച്ച് ഡെക്ക് നടപ്പിലാക്കൽ

ഒരു സ്ട്രീമിലെ ആദ്യത്തെ ആവർത്തിക്കാത്ത പ്രതീകത്തിനായുള്ള സങ്കീർണ്ണത വിശകലനം  

ഞങ്ങൾ സ്‌ട്രീമിൽ കൃത്യമായി ഒരു തവണ സഞ്ചരിച്ചതിനാൽ എല്ലാ പ്രതീകങ്ങളും ക്യൂവിലേക്ക് തള്ളുകയും ക്യൂവിൽ നിന്ന് ഒരു തവണ നീക്കംചെയ്യുകയും ചെയ്യും. അതിനാൽ
സമയ സങ്കീർണ്ണത = O (n)
ബഹിരാകാശ സങ്കീർണ്ണത = O (n)
ഇവിടെ n എന്നത് സ്ട്രീമിലെ ആകെ പ്രതീകങ്ങളുടെ എണ്ണം.

കോഡ്  

ഒരു സ്ട്രീമിലെ ആദ്യത്തെ ആവർത്തിക്കാത്ത പ്രതീകത്തിനായുള്ള ജാവ കോഡ്

import java.util.LinkedList;
import java.util.Queue;

class QueueBasedApproachForFirstNonRepeatingCharacterInAStream {
    private static void firstNonRepeatingCharacter(String stream) {
        // create a array to store frequency of characters
        int freq[] = new int[26];
        // create a queue
        Queue<Character> queue = new LinkedList<>();

        // traverse the stream character by character
        for (int i = 0; i < stream.length(); i++) {
            // current character of stream
            char curr = stream.charAt(i);
            // increase the frequency
            freq[curr - 'a']++;
            // push it to queue
            queue.add(curr);

            while (!queue.isEmpty()) {
                // check the frequency of first character in queue
                char front = queue.peek();
                if (freq[front - 'a'] == 1) {
                    // if freq is 1, print the first character
                    System.out.print(front + " ");
                    break;
                } else {
                    // else remove the first character
                    queue.poll();
                }
            }

            // if queue becomes empty, print -1
            if (queue.isEmpty()) {
                System.out.print("-1 ");
            }
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        String stream1 = "aabcddbe";
        firstNonRepeatingCharacter(stream1);

        // Example 2
        String stream2 = "abcdabcd";
        firstNonRepeatingCharacter(stream2);
    }
}
a -1 b b b b c c 
a a a a b c d -1

ഒരു സ്ട്രീമിലെ ആദ്യത്തെ ആവർത്തിക്കാത്ത പ്രതീകത്തിനായുള്ള സി ++ കോഡ്

#include<bits/stdc++.h> 
using namespace std; 

void firstNonRepeatingCharacter(string stream) {
    // create a array to store frequency of characters
    int freq[26];
    for (int i = 0; i < 26; i++) {
        freq[i] = 0;
    }
    // create a queue
    queue<char> q;
    
    // traverse the stream character by character
    for (int i = 0; i < stream.length(); i++) {
        // current character of stream
        char c = stream[i];
        // increase the frequency
        freq[c - 'a']++;
        // push it to queue
        q.push(c);
        
        while (!q.empty()) {
            // check the frequency of first character in queue
            char front = q.front();
            if (freq[front - 'a'] == 1) {
                // if freq is 1, print the first character
                cout<<front<<" ";
                break;
            } else {
                // else remove the first character
                q.pop();
            }
        }
        
        // if queue becomes empty, print -1
        if (q.size() == 0) {
            cout<<"-1 ";
        }
    }
    cout<<endl;
}

int main() {
    // Example 1
    string stream1 = "aabcddbe";
    firstNonRepeatingCharacter(stream1);

    // Example 2
    string stream2 = "abcdabcd";
    firstNonRepeatingCharacter(stream2);
    
    return 0;
}
a -1 b b b b c c 
a a a a b c d -1