Given a string s consisting of lowercase letters, for each position i in the string (0 ≤ i < n), find the first non-repeating character in the prefix s[0..i]. If no such character exists, use '#'.
Examples:
Input: s = "aabc"
Output: a#bc
Explanation:
After 'a' → first unique = 'a'
After 'aa' → no unique → '#'
After 'aab' → first unique = 'b'
After 'aabc' → first unique = 'c'
Result = a#bcInput: s = "bb"
Output: b#
Explanation:
After 'b' → first unique = 'b'
After 'bb'→ no unique → '#'
Result = b#
Try it on GfG Practice
Table of Content
[Naive Approach] Using Nested Loop - O(n2) time and O(n) space
This approach maintains a frequency count of each character using a vector. For each character in the string, it scans from the beginning to find the first non-repeating character by checking the frequency of each character up to that point. If a non-repeating character is found, it is appended to the result; otherwise,
#is appended when no such character exists. This process ensures that the first non-repeating character is identified at each step.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string firstNonRepeating(string &s){
string ans;
int n = s.size();
// frequency vector for all ASCII characters
vector<int> freq(26, 0);
// Process each character in the stream
for (int i = 0; i < n; i++){
// Update frequency for the current character
freq[s[i]-'a']++;
// Scan from the beginning to find the first non-repeating character
bool found = false;
for (int j = 0; j <= i; j++){
if (freq[s[j]-'a'] == 1){
ans.push_back(s[j]);
found = true;
break;
}
}
if (!found){
ans.push_back('#');
}
}
return ans;
}
int main() {
string s = "aabc";
string ans = firstNonRepeating(s);
cout << ans << endl;
return 0;
}
class GfG {
static String firstNonRepeating(String s) {
StringBuilder ans = new StringBuilder();
int n = s.length();
// frequency array for all ASCII characters
int[] freq = new int[26];
// Process each character in the stream
for (int i = 0; i < n; i++) {
// Update frequency for the current character
freq[s.charAt(i) - 'a']++;
// Scan from the beginning to find the
// first non-repeating character
boolean found = false;
for (int j = 0; j <= i; j++) {
if (freq[s.charAt(j) - 'a'] == 1) {
ans.append(s.charAt(j));
found = true;
break;
}
}
if (!found) {
ans.append('#');
}
}
return ans.toString();
}
public static void main(String[] args) {
String s = "aabc";
String ans = firstNonRepeating(s);
System.out.println(ans);
}
}
def firstNonRepeating(s):
ans = ''
n = len(s)
# frequency list for all ASCII characters
freq = [0] * 26
# Process each character in the stream
for i in range(n):
# Update frequency for the current character
freq[ord(s[i]) - ord('a')] += 1
# Scan from the beginning to find the
# first non-repeating character
found = False
for j in range(i + 1):
if freq[ord(s[j]) - ord('a')] == 1:
ans += s[j]
found = True
break
if not found:
ans += '#'
return ans
if __name__ == "__main__":
s = "aabc"
ans = firstNonRepeating(s)
print(ans)
using System;
using System.Text;
class GfG {
static string firstNonRepeating(string s) {
StringBuilder ans = new StringBuilder();
int n = s.Length;
// frequency array for all ASCII characters
int[] freq = new int[26];
// Process each character in the stream
for (int i = 0; i < n; i++)
{
// Update frequency for the current character
freq[s[i] - 'a']++;
// Scan from the beginning to find the first non-repeating character
bool found = false;
for (int j = 0; j <= i; j++)
{
if (freq[s[j] - 'a'] == 1)
{
ans.Append(s[j]);
found = true;
break;
}
}
if (!found)
{
ans.Append('#');
}
}
return ans.ToString();
}
public static void Main()
{
string s = "aabc";
string ans = firstNonRepeating(s);
Console.WriteLine(ans);
}
}
function firstNonRepeating(s) {
let ans = '';
let n = s.length;
// frequency array for all ASCII characters
let freq = new Array(26).fill(0);
// Process each character in the stream
for (let i = 0; i < n; i++) {
// Update frequency for the current character
freq[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
// Scan from the beginning to find the first non-repeating character
let found = false;
for (let j = 0; j <= i; j++) {
if (freq[s.charCodeAt(j) - 'a'.charCodeAt(0)] === 1) {
ans += s[j];
found = true;
break;
}
}
if (!found) {
ans += '#';
}
}
return ans;
}
// Driver Code
let s = 'aabc';
let ans = firstNonRepeating(s);
console.log(ans);
Output
a#bb
[Better Approach] Using Queue and Frequency Array - O(n) Time and O(n) Space
We use a count array of size 26 to track character frequencies and a queue to maintain their order of appearance. For each new character, we update its frequency and push it into the queue. Then, we remove characters from the front of the queue until the first non-repeating character is found, or the queue becomes empty.
#include <iostream>
#include<queue>
#include<vector>
using namespace std;
string firstNonRepeating(string& s){
string ans = "";
vector<int> count(26, 0);
queue<char> q;
for (int i = 0; i < s.length(); i++) {
// if non-repeating element found push it in queue
if (count[s[i] - 'a'] == 0) {
q.push(s[i]);
}
count[s[i] - 'a']++;
// if front element is repeating pop it from the queue
while (!q.empty() && count[q.front() - 'a'] > 1) {
q.pop();
}
// if queue is not empty append front
// element else append "#" in ans string.
if (!q.empty()) {
ans += q.front();
}
else {
ans += '#';
}
}
return ans;
}
int main()
{
string s = "aabc";
string ans = firstNonRepeating(s);
cout << ans << "\n";
return 0;
}
import java.util.Queue;
import java.util.LinkedList;
class GfG {
static String firstNonRepeating(String s) {
StringBuilder ans = new StringBuilder();
int[] count = new int[26];
Queue<Character> q = new LinkedList<>();
for (int i = 0; i < s.length(); i++) {
// if non-repeating element found push it in queue
if (count[s.charAt(i) - 'a'] == 0) {
q.add(s.charAt(i));
}
count[s.charAt(i) - 'a']++;
// if front element is repeating pop it from the queue
while (!q.isEmpty() && count[q.peek() - 'a'] > 1) {
q.poll();
}
// if queue is not empty append front
// element else append "#" in ans string.
if (!q.isEmpty()) {
ans.append(q.peek());
} else {
ans.append('#');
}
}
return ans.toString();
}
public static void main(String[] args) {
String s = "aabc";
String ans = firstNonRepeating(s);
System.out.println(ans);
}
}
from collections import deque
def firstNonRepeating(s):
ans = ""
count = [0] * 26
q = deque()
for char in s:
# if non-repeating element found push it in queue
if count[ord(char) - ord('a')] == 0:
q.append(char)
count[ord(char) - ord('a')] += 1
# if front element is repeating pop it from the queue
while q and count[ord(q[0]) - ord('a')] > 1:
q.popleft()
# if queue is not empty append front
# element else append "#" in ans string.
if q:
ans += q[0]
else:
ans += '#'
return ans
if __name__ == '__main__':
s = "aabc"
ans = firstNonRepeating(s)
print(ans)
using System;
using System.Collections.Generic;
class GfG {
static string firstNonRepeating(string s) {
string ans = "";
int[] count = new int[26];
Queue<char> q = new Queue<char>();
foreach (char c in s) {
// if non-repeating element found push it in queue
if (count[c - 'a'] == 0) {
q.Enqueue(c);
}
count[c - 'a']++;
// if front element is repeating pop it from the queue
while (q.Count > 0 && count[q.Peek() - 'a'] > 1) {
q.Dequeue();
}
// if queue is not empty append front
// element else append "#" in ans string.
if (q.Count > 0) {
ans += q.Peek();
} else {
ans += '#';
}
}
return ans;
}
static void Main() {
string s = "aabc";
string ans = firstNonRepeating(s);
Console.WriteLine(ans);
}
}
// Node class for doubly linked list
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
// Queue implemented using doubly linked list
class Queue {
constructor() {
this.front = null;
this.rear = null;
this.size = 0;
}
// Add element at the rear
enqueue(x) {
let node = new Node(x);
if (!this.rear) {
this.front = this.rear = node;
} else {
node.prev = this.rear;
this.rear.next = node;
this.rear = node;
}
this.size++;
}
// Remove element from the front
dequeue() {
if (!this.front) {
console.log("Queue is empty");
return null;
}
let val = this.front.data;
this.front = this.front.next;
if (this.front) this.front.prev = null;
else this.rear = null;
this.size--;
return val;
}
// Get front element without removing
frontElement() {
return this.front ? this.front.data : null;
}
isEmpty() {
return this.size === 0;
}
}
// Function to find first non-repeating character in a stream
function firstNonRepeating(s) {
let ans = "";
let count = new Array(26).fill(0);
let q = new Queue();
for (let i = 0; i < s.length; i++) {
let idx = s.charCodeAt(i) - 'a'.charCodeAt(0);
// if first occurrence, enqueue it
if (count[idx] === 0) {
q.enqueue(s[i]);
}
count[idx]++;
// remove repeating elements from front
while (!q.isEmpty() &&
count[q.frontElement().charCodeAt(0) - 'a'.charCodeAt(0)] > 1) {
q.dequeue();
}
// append first non-repeating or '#' if none
ans += q.isEmpty() ? '#' : q.frontElement();
}
return ans;
}
// Driver code
let s = "aabc";
let ans = firstNonRepeating(s);
console.log(ans);
Output
a#bb
[Expected Approach] Using Frequency and Last Occurrence Array- O(n) Time and O(1) Space
We maintain a frequency array to count occurrences and another array to store the first position of each character. While processing the string, we update frequencies and then check which character has frequency 1 and appeared earliest. That character becomes the current answer; if none exists, we place a '#'.
#include <iostream>
#include <vector>
using namespace std;
string firstNonRepeating(string &s) {
int n = s.size();
vector<int> freq(26, 0);
vector<int> firstPos(26, -1);
// record first occurrence for each character
for (int i = 0; i < n; i++) {
if (firstPos[s[i] - 'a'] == -1)
firstPos[s[i] - 'a'] = i;
}
string result = "";
for (int i = 0; i < n; i++) {
freq[s[i] - 'a']++;
char chosen = '#';
int earliest = n + 1;
// find earliest character with frequency 1
for (int j = 0; j < 26; j++) {
if (freq[j] == 1 && earliest > firstPos[j]) {
chosen = char(j + 'a');
earliest = firstPos[j];
}
}
result += chosen;
}
return result;
}
int main() {
string s = "aabc";
cout << firstNonRepeating(s) << endl;
return 0;
}
class GFG {
static String firstNonRepeating(String s) {
int n = s.length();
int[] freq = new int[26];
int[] firstPos = new int[26];
for (int i = 0; i < 26; i++) firstPos[i] = -1;
// record first occurrence for each character
for (int i = 0; i < n; i++) {
int idx = s.charAt(i) - 'a';
if (firstPos[idx] == -1) firstPos[idx] = i;
}
StringBuilder result = new StringBuilder();
for (int i = 0; i < n; i++) {
int idx = s.charAt(i) - 'a';
freq[idx]++;
char chosen = '#';
int earliest = n + 1;
// find earliest character with frequency 1
for (int j = 0; j < 26; j++) {
if (freq[j] == 1 && firstPos[j] < earliest) {
chosen = (char) (j + 'a');
earliest = firstPos[j];
}
}
result.append(chosen);
}
return result.toString();
}
public static void main(String[] args) {
String s = "aabc";
System.out.println(firstNonRepeating(s));
}
}
def firstNonRepeating(s):
n = len(s)
freq = [0] * 26
firstPos = [-1] * 26
# record first occurrence for each character
for i in range(n):
if firstPos[ord(s[i]) - ord('a')] == -1:
firstPos[ord(s[i]) - ord('a')] = i
result = ""
for i in range(n):
freq[ord(s[i]) - ord('a')] += 1
chosen = '#'
earliest = n + 1
# find earliest character with frequency 1
for j in range(26):
if freq[j] == 1 and earliest > firstPos[j]:
chosen = chr(j + ord('a'))
earliest = firstPos[j]
result += chosen
return result
if __name__ == '__main__':
s = "aabc"
print(firstNonRepeating(s))
using System;
using System.Text;
class GfG {
static string firstNonRepeating(string s) {
int n = s.Length;
int[] freq = new int[26];
int[] firstPos = new int[26];
Array.Fill(firstPos, -1);
// record first occurrence for each character
for (int i = 0; i < n; i++) {
if (firstPos[s[i] - 'a'] == -1)
firstPos[s[i] - 'a'] = i;
}
StringBuilder result = new StringBuilder();
for (int i = 0; i < n; i++) {
freq[s[i] - 'a']++;
char chosen = '#';
int earliest = n + 1;
// find earliest character with frequency 1
for (int j = 0; j < 26; j++)
{
if (freq[j] == 1 && earliest > firstPos[j])
{
chosen = (char)(j + 'a');
earliest = firstPos[j];
}
}
result.Append(chosen);
}
return result.ToString();
}
public static void Main()
{
string s = "aabc";
Console.WriteLine(firstNonRepeating(s));
}
}
function firstNonRepeating(s) {
let n = s.length;
let freq = new Array(26).fill(0);
let firstPos = new Array(26).fill(-1);
// record first occurrence for each character
for (let i = 0; i < n; i++) {
if (firstPos[s.charCodeAt(i) - 'a'.charCodeAt(0)] === -1)
firstPos[s.charCodeAt(i) - 'a'.charCodeAt(0)] = i;
}
let result = "";
for (let i = 0; i < n; i++) {
freq[s.charCodeAt(i) - 'a'.charCodeAt(0)]++;
let chosen = '#';
let earliest = n + 1;
// find earliest character with frequency 1
for (let j = 0; j < 26; j++) {
if (freq[j] === 1 && earliest > firstPos[j]) {
chosen = String.fromCharCode(j + 'a'.charCodeAt(0));
earliest = firstPos[j];
}
}
result += chosen;
}
return result;
}
// Driver Code
let s = "aabc";
console.log(firstNonRepeating(s));
Output
a#bb