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 = “neveropen”
Output: fInput: 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 Listvoid 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 Codeint main(){ string str = "neveropen"; // 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 = "neveropen"; // Function Call firstNonRepElement(str); } } |
Python3
# Python3 implementation to find the# first non-repeating element of the# string using Linked Listimport collections# Function to find the first# non-repeating element of the# given string using Linked Listdef 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 Codeif __name__=='__main__': str = "neveropen"; # 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 Listusing System; using System.Collections; using System.Collections.Generic;class FirstNonRepeatingElement{// Function to find the first// non-repeating element of the// given string using Linked Liststatic 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 Codepublic static void Main(string[] args){ string str = "neveropen"; // 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 Listfunction 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 Codelet str = "neveropen";// Function CallfirstNonRepElement(str);// This code is contributed by patel2127</script> |
Output
f
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Info on that Topic: geeksforgeeks.org/find-first-non-repeating-character-in-a-given-string-using-linked-list/ […]
… [Trackback]
[…] Info on that Topic: geeksforgeeks.org/find-first-non-repeating-character-in-a-given-string-using-linked-list/ […]