Find first non-repeating character in a given string using Linked List

0 0 3 minutes read

Given a string str of length L, the task is to find the first occurrence of a non-repeating character in the string.

Examples:

Input: str = “zambiatek”
Output: f

Input: str = “programmer”
Output: p

Note: Please refer this article for HashMap approach and this article as space-optimized approach.

Linked List Approach: The idea is to use Linked List to keep track of the unique elements in the string. Below is the illustration of the approach:

Iterate over the string for each character in the string and add the character in the Linked List on basis of the below conditions:
- If the character is already present in the Linked List, then remove the existing character node from the linked list.
- Otherwise, Add the character into the linked list.
Finally, the character at the first node of the linked list is the first non-repeating character of the string.

Below is the implementation of the above approach:

C++14

// C++ implementation to find the
// first non-repeating element of the
// string using Linked List
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the first
// non-repeating element of the
// given string using Linked List
void firstNonRepElement(string str)
{
    map<char, int> mpp;
 
    for(auto i:str)
    {
        mpp[i]++;
    }
 
    for(auto i:str)
    {
        if (mpp[i] == 1)
        {
            cout << i << endl;
            return;
        }
    }
    return;
}
 
// Driver Code
int main()
{
    string str = "zambiatek";
 
    // Function Call
    firstNonRepElement(str);
}
 
// This code is contributed by mohit kumar 29

Java

// Java implementation to find the 
// first non-repeating element 
// of the string using Linked List 
 
import java.util.LinkedList; 
 
public class FirstNonRepeatingElement { 
 
    // Function to find the first 
    // non-repeating element of the 
    // given string using Linked List 
    static void firstNonRepElement(String str) 
    { 
        LinkedList<Character> list 
            = new LinkedList<Character>(); 
 
        list.add(str.charAt(0)); 
 
        for (int i = 1; i < str.length(); i++) { 
            if (list.contains(str.charAt(i))) 
                list.remove(list.indexOf( 
                    str.charAt(i))); 
            else
                list.add(str.charAt(i)); 
        } 
        System.out.println(list.get(0)); 
    } 
 
    // Driver Code 
    public static void main(String[] args) 
    { 
        String str = "zambiatek"; 
 
        // Function Call 
        firstNonRepElement(str); 
    } 
}

Python3

# Python3 implementation to find the
# first non-repeating element of the
# string using Linked List
import collections
 
# Function to find the first
# non-repeating element of the
# given string using Linked List
def firstNonRepElement(str):
     
    # Make list as a linkedlist
    list = collections.deque()# linkedlist
 
    list.append(str[0])
 
    for i in range(len(str)):
        if str[i] in list:
            list.remove(str[i])
        else:
            list.append(str[i])
             
    print(list[0])
 
# Driver Code
if __name__=='__main__':
     
    str = "zambiatek";
     
    # Function Call
    firstNonRepElement(str); 
 
# This code is contributed by pratham76

C#

// C# implementation to find the
// first non-repeating element
// of the string using Linked List
using System; 
using System.Collections; 
using System.Collections.Generic;
 
class FirstNonRepeatingElement{
 
// Function to find the first
// non-repeating element of the
// given string using Linked List
static void firstNonRepElement(string str)
{
    LinkedList<char> list = new LinkedList<char>();
 
    list.AddLast(str[0]);
 
    for(int i = 1; i < str.Length; i++) 
    {
        if (list.Contains(str[i]))
            list.Remove(str[i]);
        else
            list.AddLast(str[i]);
    }
    Console.Write(list.First.Value);
}
 
// Driver Code
public static void Main(string[] args)
{
    string str = "zambiatek";
 
    // Function call
    firstNonRepElement(str);
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
// Javascript implementation to find the
// first non-repeating element
// of the string using Linked List
 
    // Function to find the first
    // non-repeating element of the
    // given string using Linked List
function firstNonRepElement(str)
{
    let list = [];
  
        list.push(str[0]);
  
        for (let i = 1; i < str.length; i++)
        {
            if (list.includes(str[i]))
                list.splice(list.indexOf(str[i]),1);
            else
                list.push(str[i]);
             
        }
        document.write(list[0]);
}
 
// Driver Code
let str = "zambiatek";
 
// Function Call
firstNonRepElement(str);
 
// This code is contributed by patel2127
</script>

Output

Performance Analysis:

Time Complexity: O(N * 26)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!