Dado un flujo de caracteres, tenemos que encontrar el primer carácter que no se repite cada vez que se inserta un carácter en el flujo.
Ejemplos:
C++
// C++ program for a Queue based approach
// to find first non-repeating character
#include <bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
// function to find first non repeating
// character of sa stream
void firstnonrepeating(char str[])
{
queue<char> q;
int charCount[MAX_CHAR] = { 0 };
// traverse whole stream
for (int i = 0; str[i]; i++) {
// push each character in queue
q.push(str[i]);
// increment the frequency count
charCount[str[i] - 'a']++;
// check for the non repeating character
while (!q.empty()) {
if (charCount[q.front() - 'a'] > 1)
q.pop();
else {
cout << q.front() << " ";
break;
}
}
if (q.empty())
cout << -1 << " ";
}
cout << endl;
}
// Driver function
int main()
{
char str[] = "aabc";
firstnonrepeating(str);
return 0;
}
Java
// Java Program for a Queue based approach
// to find first non-repeating character
import java.util.LinkedList;
import java.util.Queue;
public class NonReapatingCQueue {
final static int MAX_CHAR = 26;
// function to find first non repeating
// character of stream
static void firstNonRepeating(String str)
{
// count array of size 26(assuming
// only lower case characters are present)
int[] charCount = new int[MAX_CHAR];
// Queue to store Characters
Queue<Character> q = new LinkedList<Character>();
// traverse whole stream
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
// push each character in queue
q.add(ch);
// increment the frequency count
charCount[ch - 'a']++;
// check for the non repeating character
while (!q.isEmpty()) {
if (charCount[q.peek() - 'a'] > 1)
q.remove();
else {
System.out.print(q.peek() + " ");
break;
}
}
if (q.isEmpty())
System.out.print(-1 + " ");
}
System.out.println();
}
// Driver function
public static void main(String[] args)
{
String str = "aabc";
firstNonRepeating(str);
}
}
// This code is Contributed by Sumit Ghosh
Python3
# Python3 program for a Queue based approach
# to find first non-repeating character
from queue import Queue
# function to find first non
# repeating character of sa Stream
def firstnonrepeating(Str):
global MAX_CHAR
q = Queue()
charCount = [0] * MAX_CHAR
# traverse whole Stream
for i in range(len(Str)):
# push each character in queue
q.put(Str[i])
# increment the frequency count
charCount[ord(Str[i]) -
ord('a')] += 1
# check for the non repeating
# character
while (not q.empty()):
if (charCount[ord(q.queue[0]) -
ord('a')] > 1):
q.get()
else:
print(q.queue[0], end = " ")
break
if (q.empty()):
print(-1, end = " ")
print()
# Driver Code
MAX_CHAR = 26
Str = "aabc"
firstnonrepeating(Str)
# This code is contributed by PranchalK
C#
using System;
using System.Collections.Generic;
// C# Program for a Queue based approach
// to find first non-repeating character
public class NonReapatingCQueue
{
public const int MAX_CHAR = 26;
// function to find first non repeating
// character of stream
public static void firstNonRepeating(string str)
{
// count array of size 26(assuming
// only lower case characters are present)
int[] charCount = new int[MAX_CHAR];
// Queue to store Characters
LinkedList<char> q = new LinkedList<char>();
// traverse whole stream
for (int i = 0; i < str.Length; i++)
{
char ch = str[i];
// push each character in queue
q.AddLast(ch);
// increment the frequency count
charCount[ch - 'a']++;
// check for the non repeating character
while (q.Count > 0)
{
if (charCount[q.First.Value - 'a'] > 1)
{
q.RemoveFirst();
}
else
{
Console.Write(q.First.Value + " ");
break;
}
}
if (q.Count == 0)
{
Console.Write(-1 + " ");
}
}
Console.WriteLine();
}
// Driver function
public static void Main(string[] args)
{
string str = "aabc";
firstNonRepeating(str);
}
}
//This code is contributed by Shrikant13
Javascript
<script>
// JavaScript Program for a Queue based approach
// to find first non-repeating character
const MAX_CHAR = 26;
// function to find first non repeating
// character of stream
function firstNonRepeating(str) {
// count array of size 26(assuming
// only lower case characters are present)
var charCount = new Array(MAX_CHAR).fill(0);
// Queue to store Characters
var q = [];
// traverse whole stream
for (var i = 0; i < str.length; i++) {
var ch = str[i];
// push each character in queue
q.push(ch);
// increment the frequency count
charCount[ch.charCodeAt(0) - "a".charCodeAt(0)]++;
// check for the non repeating character
while (q.length > 0) {
if (charCount[q[0].charCodeAt(0) -
"a".charCodeAt(0)] > 1) {
q.shift();
} else {
document.write(q[0] + " ");
break;
}
}
if (q.length == 0) {
document.write(-1 + " ");
}
}
document.write("<br>");
}
// Driver function
var str = "aabc";
firstNonRepeating(str);
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA