ריי באזירט צוגאַנג פֿאַר ערשטער ניט-ריפּיטינג כאַראַקטער אין אַ טייַך


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן פליפּקאַרט מייקראָסאָפֿט PayU יאַהאָאָ
האַש לינקעד-רשימה ריי שטריקל

פּראָבלעם סטאַטעמענט

די פּראָבלעם "ריי באזירט צוגאַנג פֿאַר ערשטער ניט-ריפּיטינג כאַראַקטער אין אַ טייַך" שטאַטן אַז איר באַקומען אַ טייַך מיט קליין קאַסעס אותיות, געפֿינען די ערשטער ניט-ריפּיטינג כאַראַקטער ווען אַ נייַע כאַראַקטער איז מוסיף צו די טייַך, און אויב עס איז קיין ניט-ריפּיטינג כאַראַקטער צוריקקומען -1.

ביישפילן

aabcddbe
a -1 b b b b c c

דערקלערונג: ווי מיר קענען זען אַז רעזולטאַט האט דער ערשטער ניט-ריפּיטינג כאַראַקטער אומעטום אַחוץ די רגע אינדעקס. ביז אינדעקס 2, אַלע אותיות האָבן שוין ריפּיטיד. אַזוי, -1 איז געדרוקט ביי אינדעקס 2.

abcdabcd
a a a a b c d -1

 

ריי באזירט צוגאַנג פֿאַר ערשטער ניט-ריפּיטינג כאַראַקטער אין אַ טייַך

אַלגערידאַם פֿאַר דער ערשטער ניט-ריפּיטינג כאַראַקטער אין אַ טייַך

די אויבן אויבן פּראָבלעם קענען זיין סאַלווד מיט אַ ריי. אַזוי, מיר נאָר דאַרפֿן צו האַלטן אַ ריי פון אותיות און אַן מענגע פון אָפטקייַט. די מענגע סטאָרז די אָפטקייַט פון יעדער כאַראַקטער אין די טייַך.
אזוי פֿאַר יעדער כאַראַקטער אין די טייַך. און דעריבער פאַרגרעסערן די אָפטקייַט פון דעם כאַראַקטער און שטופּן עס צו די ריי. קוק די כאַראַקטער אין די אָנהייב פון די ריי, אויב די אָפטקייַט פון דעם כאַראַקטער איז 1, צוריקקומען דעם כאַראַקטער. אַנדערש, קנאַל אויס די כאַראַקטער און טשעק פֿאַר ווייַטער כאַראַקטער. אויב די ריי ווערט ליידיק, צוריקקומען -1 און פאָרזעצן צו פּראָצעס אנדערע אותיות אין דעם טייַך.

  1. שאַפֿן אַ ריי פון אותיות און אַ מענגע וואָס סטאָרז די אָפטקייַט פון יעדער כאַראַקטער.
  2. פּראָצעס די ינפּוץ פון דעם טייַך איינער דורך איינער.
  3. פֿאַר קראַנט כאַראַקטער ינפּוט אין טייַך, פאַרגרעסערן די אָפטקייַט און שטופּן עס צו די ריי.
  4. קאָנטראָלירן די כאַראַקטער אין פראָנט פון ריי, אויב די אָפטקייַט פון דעם כאַראַקטער איז 1, דרוק דעם כאַראַקטער, אַנדערש אַראָפּנעמען דער ערשטער כאַראַקטער אין דער ריי און איבערחזרן שריט 4.
  5. אויב ריי ווערט ליידיק בעשאַס שריט 4, דרוקן -1 און פאָרזעצן צו פּראָצעס ווייַטער כאַראַקטער.

קאַמפּלעקסיטי אַנאַליסיס פֿאַר דער ערשטער ניט-ריפּיטינג כאַראַקטער אין אַ טייַך

זינט מיר האָבן דורכגעקאָכט דעם טייַך פּונקט אַמאָל און יעדער כאַראַקטער קען זיין פּושט צו די ריי און אַוועקגענומען פון די ריי פּונקט אַמאָל. אַזוי
צייט קאַמפּלעקסיטי = אָ (N)
ספעיס קאַמפּלעקסיטי = אָ (N)
וווּ n איז די גאַנץ נומער פון אותיות אין דעם טייַך.

קאָדעקס

Java קאוד פאר ערשטן, ניט-ריפּיטינג כאַראַקטער אין אַ טייַך

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

C ++ קאָד פֿאַר ערשטער ניט-ריפּיטינג כאַראַקטער אין אַ טייַך

#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