**Problem Statement:** Given a string, find the leftmost non-repeating character of the string. i.e The first character that does not appear again in the further string.

**Examples:**

Example 1:Input:takeUforwardOutput: tExplanation:Character ‘t’ is the left-most non-repeating character or the first non-repeating character.

Example 2:Input:EngineerOutput: gExplanation:Character ‘g’ is the left-most non-repeating character or the first non-repeating character.

**Solution**

** Disclaimer**:

*Don’t jump directly to the solution, try it out yourself first.*

**Solution 1: Naive approach**

**Approach**:

- Select the
**first character**of the string and compare it with every other character in the string. - If the current character does not match with any of the further characters in the string then immediately
**return / Print**that character. - Else, repeat the steps 1st and 2nd until the whole string is traversed or until we got out an answer.
- if all the characters are traversed or the string is empty then
**return or print -1**. - Return the answer.

**Code**:

## C++ Code

```
#include <iostream>
using namespace std;
int firstNonRepeating(string str) {
for (int i = 0; i < str.size(); i++) {
int flag = 0;
for (int j = 0; j < str.size(); j++) {
if (i != j && str[i] == str[j]) {
flag = 1;
break;
}
}
if (flag == 0) {
return i;
}
}
return -1;
}
int main() {
string str = "takeuforward";
int index = firstNonRepeating(str);
if (index == -1)
cout << "Either all characters are repeating or "
"string is empty";
else
cout << "First non-repeating character is " <<
str[index];
getchar();
return 0;
}
```

**Output**: First non-repeating character is t

**Time Complexity: O(N^2)**

**Space Complexity: O(1)**

## Java Code

```
class TUF {
static int firstNonRepeating(String str) {
for (int i = 0; i < str.length(); i++) {
int flag = 0;
for (int j = 0; j < str.length(); j++) {
if (i != j && str.charAt(i) == str.charAt(j)) {
flag = 1;
break;
}
}
if (flag == 0) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
String str = "takeuforward";
int index = firstNonRepeating(str);
System.out.println(
index == -1 ?
"Either all characters are repeating or string " +
"is empty" :
"First non-repeating character is " +
str.charAt(index));
}
}
```

**Output**: First non-repeating character is t

**Time Complexity: O(N^2)**

**Space Complexity: O(1)**

**Solution 2: Using Frequency Array**

**Approach**:

- Make a count array of size 256
*i.e all the alphabets and symbols.* - We will initialize all the elements in this array to -1.
- Then loop through the string character by character and check if the frequency array element with this character has it’s index as -1 or not.
- If it is -1 then change it to
**‘i’**and if it is not -1 then this means that this character has already appeared before, so change it to -2.*i.e (our looping variable)* - In the end all the repeating characters will be changed to -2 and all non-repeating characters will contain the index where they occur. Now we can just loop through all the non-repeating characters and find the minimum index or the first index.

**Code:**

## C++ Code

```
# include<bits/stdc++.h>
using namespace std;
int firstNonRepeating(string str) {
int fi[256]; // frequency array
for(int i = 0; i<256; i++)
{
fi[i] = -1; // initalizing every index of frequency array with -1.
}
// sets all repeating characters to -2 and non-repeating characters
// contain the index where they occur
for(int i = 0; i<str.length(); i++)
{
if(fi[str[i]] == -1)
{
fi[str[i]] = i;
}
else
{
fi[str[i]] = -2;
}
}
// If this character is not -1 or -2 then it
// means that this character occurred only once
// so find the min index of all characters that
// occur only once, that's our first index
int res = INT_MAX;
for(int i = 0; i<256; i++)
{
if(fi[i] >= 0)
{
res = min(res, fi[i]); // finding the minimum index of
//non-repeating character.
}
}
// if res remains INT_MAX, it means there are no
// characters that repeat only once or the string is empty
if(res == INT_MAX)
{
return -1;
}
return res;
}
int main(){
string str;
str = "takeuforward";
int firstIndex = firstNonRepeating(str);
if (firstIndex == -1)
cout<<"Either all characters are repeating or string is empty";
else
cout<<"First non-repeating character is "<< str[firstIndex];
return 0;
}
```

**Output:** First non-repeating character is t

**Time Complexity: O(N)**

**Space Complexity: O(1) **

*Reason: 256 is a constant so Space complexity is O(1).*

## Java Code

```
public class TUF {
public static int firstNonRepeating(String str) {
int[] fi = new int[256]; // frequency array
// initializing all elements to -1
for (int i = 0; i < 256; i++) {
fi[i] = -1;
}
// sets all repeating characters to -2 and non-repeating characters
// contain the index where they occur
for (int i = 0; i < str.length(); i++) {
if (fi[str.charAt(i)] == -1) {
fi[str.charAt(i)] = i;
} else {
fi[str.charAt(i)] = -2;
}
}
// If this character is not -1 or -2 then it
// means that this character occurred only once
// so find the min index of all characters that
// occur only once, that's our first index
int res = Integer.MAX_VALUE;
for (int i = 0; i < 256; i++) {
if (fi[i] >= 0) {
res = Math.min(res, fi[i]);
}
}
// if res remains Integer.MAX_VALUE, it means there are no
// characters that repeat only once or the string is empty
if (res == Integer.MAX_VALUE) {
return -1;
}
return res;
}
public static void main(String args[]) {
String str;
str = "takeuforward";
int firstIndex = firstNonRepeating(str);
if (firstIndex == -1) {
System.out.println("Either all characters are repeating or string is empty");
} else {
System.out.println("First non-repeating character is "+str.charAt(firstIndex));
}
}
}
```

**Output:** First non-repeating character is t

**Time Complexity: O(N)**

**Space Complexity: O(1) **

*Reason: 256 is a constant so Space complexity is O(1).*

Special thanks toplease check out this articlefor contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam,Abhishek Yadav