Encuentre el primer carácter que no se repite en una string dada usando la Lista vinculada

Dada una string str de longitud L , la tarea es encontrar la primera aparición de un carácter que no se repite en la string.

Ejemplos:

Entrada: str = «geeksforgeeks»
Salida: f

Entrada: str = “programador”
Salida: p
 

Nota: Consulte este artículo para el enfoque de HashMap y este artículo como enfoque optimizado para el espacio.

Enfoque de lista enlazada:   la idea es usar la lista enlazada para realizar un seguimiento de los elementos únicos en la string. A continuación se muestra la ilustración del enfoque:

• Iterar sobre la string para cada carácter de la string y agregar el carácter en la Lista vinculada en función de las siguientes condiciones:
  • Si el carácter ya está presente en la lista vinculada, elimine el Node de carácter existente de la lista vinculada.
  • De lo contrario, agregue el carácter a la lista vinculada.
• Finalmente, el carácter en el primer Node de la lista enlazada es el primer carácter no repetido de la string.

A continuación se muestra la implementación del enfoque anterior: 

// 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 = "geeksforgeeks";
 
    // Function Call
    firstNonRepElement(str);
}
 
// This code is contributed by mohit kumar 29

// 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 = "geeksforgeeks";
 
        // Function Call
        firstNonRepElement(str);
    }
}

# 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 = "geeksforgeeks";
     
    # Function Call
    firstNonRepElement(str);
 
# This code is contributed by pratham76

// 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 = "geeksforgeeks";
 
    // Function call
    firstNonRepElement(str);
}
}
 
// This code is contributed by rutvik_56

<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 = "geeksforgeeks";
 
// Function Call
firstNonRepElement(str);
 
// This code is contributed by patel2127
</script>

f

Análisis de rendimiento:

• Complejidad de tiempo: O (N * 26)
• Espacio Auxiliar: O(N)