Home » Interview Questions » String Interview Questions » Find First non-repeating character in a string

Find First non-repeating character in a string


()

In the given stream of characters(string), find the first non-repeating character.

Example

Input string : ababcef

Output : c

Time complexity : O(1)

Algorithm

Here we use doubly linked list, The DLL contains all non-repeating character in order.

1. Create an empty DLL, array inDLL[] and repeated[] of size of asci values.

2. inDLL[] contains pointers of DLL nodes.inDLL[x] has pointer of x, else NULL.

3. Repeated[] array has bool values, repeated[x] is true if x is repeated two or more times, else false.

4. Initialize inDLL[] with NULL values and repeated[x] is false.

5. The head of DLL is first non-repeating character.

6. For every new character x,

   a) If repeated[x] is true, ignore this character.

b) If repeated[x] is false and inDLL[x] is Null Append x to DLL and store new DLL node in inDLL[x].

c) If repeadted[x] is false and inDLL[x] is not Null, get DLL node of x using inDLL[x] and remove the node. mark inDLL[x] as Null and repeated[x] as true.

C++ Program

#include <bits/stdc++.h>

#define ASCII_VALUES 256
using namespace std;
 
// A linked list DLLNode
struct DLLNode
{
    char data;
    struct DLLNode *next, *prev;
};
//function to insert node at beginning of DLL
void insertAtbeginning(struct DLLNode **head_ref, struct DLLNode **tail_ref,char x)
{
    struct DLLNode *temp = new DLLNode;
    temp->data = x;
    temp->prev = temp->next = NULL;
    if (*head_ref == NULL)
    {
        *head_ref = *tail_ref = temp;
        return;
    }
    (*tail_ref)->next = temp;
    temp->prev = *tail_ref;
    *tail_ref = temp;
}
 
//Function to remove node
void DeleteNode(struct DLLNode **head_ref, struct DLLNode **tail_ref,struct DLLNode *temp)
{
    if (*head_ref == NULL)
    {
        return;
    }
    if (*head_ref == temp)
    {
        *head_ref = (*head_ref)->next;
    }
    if(*tail_ref == temp)
    {
        *tail_ref = (*tail_ref)->prev;
    }
    if (temp->next != NULL)
    {
        temp->next->prev = temp->prev;
    }
    if (temp->prev != NULL)
    {
        temp->prev->next = temp->next;
    }
    delete(temp);
}
 
void FindFirst()
{
    struct DLLNode *inDLL[ASCII_VALUES];
    bool repeated[ASCII_VALUES];
    // Initialize the above two arrays
    struct DLLNode *head = NULL, *tail = NULL;
    for (int i = 0; i < ASCII_VALUES; i++)
    {
        inDLL[i] = NULL;
        repeated[i] = false;
    }
    //Traverse for all charcters
    char string[] = "ababcef";
    for (int i = 0; string[i]; i++)
    {
        char x = string[i];
        cout<<"Reading charcter "<<x<<" from string \n";
        //If charchter occurred less than twice.
        if (!repeated[x])
        {
            if (inDLL[x] == NULL)//If it  is not in DLL add it in beginning
            {
                insertAtbeginning(&head, &tail, string[i]);
                inDLL[x] = tail;
            }
            else//If its already there remove this character from DLL
            {
                DeleteNode(&head, &tail, inDLL[x]);
                inDLL[x] = NULL;
                repeated[x] = true; // Also mark it as repeated
            }
        }
        if (head != NULL)//Current first non-repating character (head)
        {
            cout<<"First non-repeating character till now: "<<head->data<<endl;
        }
    }
}
 
//Main function
int main()
{
    FindFirst();
    return 0;
}

Try It

READ  Valid Number

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions