પ્રવાહમાં પ્રથમ બિન-પુનરાવર્તન પાત્ર માટે કતાર આધારિત અભિગમ


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન ફ્લિપકાર્ટ માઈક્રોસોફ્ટ પે યાહૂ
હેશ લિંક્ડ-સૂચિ કતાર શબ્દમાળા

સમસ્યા નિવેદન

સમસ્યા "પ્રથમ પ્રવાહમાં પુનરાવર્તિત પાત્ર માટે કતાર આધારિત અભિગમ" જણાવે છે કે તમને લોઅર કેસ ધરાવતો પ્રવાહ આપવામાં આવે છે. અક્ષરો, જ્યારે પણ પ્રવાહમાં કોઈ નવું પાત્ર ઉમેરવામાં આવે ત્યારે પ્રથમ બિન-પુનરાવર્તન પાત્ર શોધો, અને જો ત્યાં પુનરાવર્તિત પાત્ર ન હોય તો -1.

ઉદાહરણો

aabcddbe
a -1 b b b b c c

સમજૂતી: આપણે જોઈ શકીએ છીએ કે આઉટપુટ બીજા અનુક્રમણિકા સિવાય સર્વત્ર બિન-પુનરાવર્તન પાત્ર ધરાવે છે. પરંતુ અનુક્રમણિકા 2 સુધી બધા અક્ષરો પુનરાવર્તિત થયા છે. તેથી, -1 અનુક્રમણિકા 2 પર મુદ્રિત છે.

abcdabcd
a a a a b c d -1

 

પ્રવાહમાં પ્રથમ બિન-પુનરાવર્તન પાત્ર માટે કતાર આધારિત અભિગમ

પ્રવાહમાં પ્રથમ બિન-પુનરાવર્તિત પાત્ર માટે અલ્ગોરિધમનો

ઉપરોક્ત સમસ્યા a નો ઉપયોગ કરીને ઉકેલી શકાય છે કતાર. તેથી, આપણે ફક્ત અક્ષરોની કતાર જાળવવાની જરૂર છે, અને એક એરે આવર્તન. એરે પ્રવાહના દરેક પાત્રની આવર્તન સંગ્રહિત કરે છે.
આમ પ્રવાહના દરેક પાત્ર માટે. અને પછી તે પાત્રની આવર્તન વધારવા અને તેને કતારમાં દબાણ કરો. કતારની શરૂઆતમાં અક્ષરને તપાસો, જો તે પાત્રની આવર્તન 1 હોય, તો અક્ષર પાછો. બાકી, અક્ષરને પ outપ આઉટ કરો અને આગલા પાત્ર માટે તપાસો. જો કતાર ખાલી થઈ જાય, તો -1 પર પાછા ફરો અને પ્રવાહમાં અન્ય અક્ષરો પર પ્રક્રિયા કરવાનું ચાલુ રાખો.

  1. અક્ષરોની કતાર અને એક એરે બનાવો જે દરેક પાત્રની આવર્તન સંગ્રહિત કરે છે.
  2. એક પછી એક પ્રવાહના ઇનપુટ્સની પ્રક્રિયા.
  3. પ્રવાહમાં વર્તમાન પાત્ર ઇનપુટ માટે, આવર્તન વધારો અને તેને કતારમાં દબાણ કરો.
  4. કતારની આગળના પાત્રને તપાસો, જો તે પાત્રની આવર્તન 1 હોય, તો અક્ષર છાપો, નહીં તો કતારમાં પ્રથમ અક્ષર કા removeો અને પગલું 4 પુનરાવર્તિત કરો.
  5. જો પગલું 4 દરમિયાન કતાર ખાલી થઈ જાય, તો -1 છાપો અને આગલા પાત્રની પ્રક્રિયા ચાલુ રાખો.

પ્રવાહમાં પ્રથમ બિન-પુનરાવર્તન પાત્ર માટે જટિલતા વિશ્લેષણ

અમે બરાબર એક વાર પ્રવાહને પસાર કર્યો હોવાથી અને દરેક પાત્રને કતાર તરફ ધકેલી દેવામાં આવશે અને બરાબર એક વાર કતારથી દૂર કરવામાં આવશે. તેથી
સમય જટિલતા = ઓ (એન)
અવકાશ જટિલતા = ઓ (એન)
જ્યાં 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