Find the count of characters that are not repeated in the string in python

In this tutorial, we will learn writing the python program to print all characters of the string which are not repeating. We can say the character are available only one time in string.

Nội dung chính Show

Problem Statement
Algorithm to find all non repeating characters in the string
Python code to find all non repeating characters in the string
How do you count non
How do you find non
How do you get a non repeated value in Python?
How do I find a repeated character in a string in Python?

Page Contents

Problem Statement
Our logic to find all non repeating characters in the string
Algorithm to find all non repeating characters in the string
Python code to find all non repeating characters in the string

Problem Statement

Take any string as an input from the user and check if any character in the string is repeating or not. if it is not repeating then print that character as output.

For example:

Case1: If the user inputs the string ‘pythonprogramming’

Then the output should be ‘ythai’, where there is no character that is repeating.

Case2: If the user inputs the string ‘quescoll’

Then the output should be ‘quesco’, where there is no character that is repeating.

Our program will take a string as an input from the user.
Iterate the character of the input string to check if the character is repeating or not, to achieve this we use the concept of ‘nested loop’.
The output is in the form of a string, where all the non-repeating characters are concatenated together using concatenation methods.

Algorithm to find all non repeating characters in the string

Step1: Start
Step2: Take a string as an input from the user
Step3: Create an empty string result=”” to store non-repeating characters in the string.
Step4: iterate through each character of the string
Step5: Declare a variable count=0 to count appearance of each character of the string
Step6: for j in string:
if i==j:
increment count to 1
if count is greater than one:
break the current iteration of nested loop
if count is equal to 1:
concatenate the character with the empty string, result
Step7: print result as the output of our program
Step8: Stop

Python code to find all non repeating characters in the string

Output:

Explanation:

For the input string ‘aabbcdeeffgh’, as the characters ‘a’, ‘b’, ‘e’, and ‘f’ are repeating but ‘c’, ‘d’, ‘g’ and ‘h’ are not repeating so the generated output should be ‘cdgf’.

Given a string, find the first non-repeating character in it. For example, if the input string is “GeeksforGeeks”, then the output should be ‘f’ and if the input string is “GeeksQuiz”, then the output should be ‘G’.

Example:

Input: "geeksforgeeks"
Explanation:
Step 1: Construct a character count array 
        from the input string.
   ....
  count['e'] = 4
  count['f'] = 1
  count['g'] = 2
  count['k'] = 2
  ……

Step 2: Get the first character who's 
        count is 1 ('f').

Method #1: HashMap and Two-string method traversals.

A character is said to be non-repeating if its frequency in the string is unit. Now for finding such characters, one needs to find the frequency of all characters in the string and check which character has unit frequency. This task could be done efficiently using a hash_map which will map the character to there respective frequencies and in which we can simultaneously update the frequency of any character we come across in constant time. The maximum distinct characters in the ASCII system are 256. So hash_map has a maximum size of 256. Now read the string again and the first character which we find has a frequency as unity is the answer.

Algorithm:

Make a hash_map which will map the character to there respective frequencies.
Traverse the given string using a pointer.
Increase the count of current character in the hash_map.
Now traverse the string again and check whether the current character hasfrequency=1.
If the frequency>1 continue the traversal.
Else break the loop and print the current character as the answer.

Pseudo Code :

for ( i=0 to str.length())
hash_map[str[i]]++;

for(i=0 to str.length())
  if(hash_map[str[i]]==1)
  return str[i]

Below is the implementation of the above approach:

C++

#include <iostream>

using namespace std;

#define NO_OF_CHARS 256

int* getCharCountArray(char* str)

{

int* count = (int*)calloc(sizeof(int), NO_OF_CHARS);

int i;

for (i = 0; *(str + i); i++)

count[*(str + i)]++;

return count;

}

int firstNonRepeating(char* str)

{

int* count = getCharCountArray(str);

int index = -1, i;

for (i = 0; *(str + i); i++) {

if (count[*(str + i)] == 1) {

index = i;

break;

}

free(count);

return index;

}

int main()

{

char str[] = "geeksforgeeks";

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;

}

C

#include <stdio.h>

#include <stdlib.h>

#define NO_OF_CHARS 256

int* getCharCountArray(char* str)

{

int* count = (int*)calloc(sizeof(int), NO_OF_CHARS);

int i;

for (i = 0; *(str + i); i++)

count[*(str + i)]++;

return count;

}

int firstNonRepeating(char* str)

{

int* count = getCharCountArray(str);

int index = -1, i;

for (i = 0; *(str + i); i++) {

if (count[*(str + i)] == 1) {

index = i;

break;

}

free(count);

return index;

}

int main()

{

char str[] = "geeksforgeeks";

int index = firstNonRepeating(str);

if (index == -1)

printf("Either all characters are repeating or "

"string is empty");

else

printf("First non-repeating character is %c",

str[index]);

getchar();

return 0;

}

Java

class GFG {

static final int NO_OF_CHARS = 256;

static char count[] = new char[NO_OF_CHARS];

static void getCharCountArray(String str)

{

for (int i = 0; i < str.length(); i++)

count[str.charAt(i)]++;

}

static int firstNonRepeating(String str)

{

getCharCountArray(str);

int index = -1, i;

for (i = 0; i < str.length(); i++) {

if (count[str.charAt(i)] == 1) {

index = i;

break;

}

return index;

}

public static void main(String[] args)

{

String str = "geeksforgeeks";

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));

}

Python3

NO_OF_CHARS = 256

def getCharCountArray(string):

count = [0] * NO_OF_CHARS

for i in string:

count[ord(i)]+= 1

return count

def firstNonRepeating(string):

count = getCharCountArray(string)

index = -1

k = 0

for i in string:

if count[ord(i)] == 1:

index = k

break

k += 1

return index

string = "geeksforgeeks"

index = firstNonRepeating(string)

if index == 1:

print ("Either all characters are repeating or string is empty")

else:

print ("First non-repeating character is" , string[index])

C#

using System;

using System.Globalization;

class GFG {

static int NO_OF_CHARS = 256;

static char[] count = new char[NO_OF_CHARS];

static void getCharCountArray(string str)

{

for (int i = 0; i < str.Length; i++)

count[str[i]]++;

}

static int firstNonRepeating(string str)

{

getCharCountArray(str);

int index = -1, i;

for (i = 0; i < str.Length; i++) {

if (count[str[i]] == 1) {

index = i;

break;

}

return index;

}

public static void Main()

{

string str = "geeksforgeeks";

int index = firstNonRepeating(str);

Console.WriteLine(index == -1 ? "Either "

+ "all characters are repeating or string "

+ "is empty"

: "First non-repeating character"

+ " is " + str[index]);

}

PHP

<?php

$NO_OF_CHARS = 256;

$count=array_fill(0, 200, 0);

function getCharCountArray($str)

{

global $count;

for ($i = 0;

$i < strlen($str); $i++)

$count[ord($str[$i])]++;

}

function firstNonRepeating($str)

{

global $count;

getCharCountArray($str);

$index = -1;

for ($i = 0;

$i < strlen($str); $i++)

{

if ($count[ord($str[$i])] == 1)

{

$index = $i;

break;

}

return $index;

}

$str = "geeksforgeeks";

$index = firstNonRepeating($str);

if($index == -1)

echo "Either all characters are" .

" repeating or string is empty";

else

echo "First non-repeating ".

"character is ".

$str[$index];

?>

Output

First non-repeating character is f

Can this be done by traversing the string only once?
The above approach takes O(n) time, but in practice, it can be improved. The first part of the algorithm runs through the string to construct the count array (in O(n) time). This is reasonable. But the second part about running through the string again just to find the first non-repeater is not a good practice.
In real situations, the string is expected to be much larger than your alphabet. Take DNA sequences, for example, they could be millions of letters long with an alphabet of just 4 letters. What happens if the non-repeater is at the end of the string? Then we would have to scan for a long time (again).

Method #2: HashMap and single string traversal

Make a count array instead of hash_map of maximum number of characters(256). We can augment the count array by storing not just counts but also the index of the first time you encountered the character e.g. (3, 26) for ‘a’ meaning that ‘a’ got counted 3 times and the first time it was seen is at position 26. So when it comes to finding the first non-repeater, we just have to scan the count array, instead of the string. Thanks to Ben for suggesting this approach.

Algorithm :

Make a count_array which will have two fields namely frequency, first occurrence of a character.
The size of count_array is ‘256’.
Traverse the given string using a pointer.
Increase the count of current character and update the occurrence.
Now here’s a catch, the array will contain valid first occurrence of the character which has frequency has unity otherwise the first occurrence keeps updating.
Now traverse the count_array and find the character which has least value of first occurrence and frequency value as unity.
Return the character

Pseudo Code :

for ( i=0 to str.length())
count_arr[str[i]].first++;
count_arr[str[i]].second=i;

int res=INT_MAX;
for(i=0 to count_arr.size())
  if(count_arr[str[i]].first==1)
  res=min(min, count_arr[str[i]].second)

return res

Implementation:

C++

#include <bits/stdc++.h>

using namespace std;

#define NO_OF_CHARS 256

int firstNonRepeating(char* str)

{

pair<int, int> arr[NO_OF_CHARS];

for (int i = 0; str[i]; i++) {

(arr[str[i]].first)++;

arr[str[i]].second = i;

}

int res = INT_MAX;

for (int i = 0; i < NO_OF_CHARS; i++)

if (arr[i].first == 1)

res = min(res, arr[i].second);

return res;

}

int main()

{

char str[] = "geeksforgeeks";

int index = firstNonRepeating(str);

if (index == INT_MAX)

printf("Either all characters are "

"repeating or string is empty");

else

printf("First non-repeating character"

" is %c",

str[index]);

return 0;

}

C

#include <limits.h>

#include <stdio.h>

#include <stdlib.h>

#define NO_OF_CHARS 256

struct countIndex {

int count;

int index;

};

struct countIndex* getCharCountArray(char* str)

{

struct countIndex* count = (struct countIndex*)calloc(

sizeof(struct countIndex), NO_OF_CHARS);

int i;

for (i = 0; *(str + i); i++) {

(count[*(str + i)].count)++;

if (count[*(str + i)].count == 1)

count[*(str + i)].index = i;

}

return count;

}

int firstNonRepeating(char* str)

{

struct countIndex* count

= getCharCountArray(str);

int result = INT_MAX, i;

for (i = 0; i < NO_OF_CHARS; i++) {

if (count[i].count == 1

&& result > count[i].index)

result = count[i].index;

}

free(count);

return result;

}

int main()

{

char str[] = "geeksforgeeks";

int index = firstNonRepeating(str);

if (index == INT_MAX)

printf("Either all characters are"

" repeating or string is empty");

else

printf("First non-repeating character"

" is %c",

str[index]);

getchar();

return 0;

}

Java

import java.util.*;

class CountIndex {

int count, index;

public CountIndex(int index)

{

this.count = 1;

this.index = index;

}

public void incCount()

{

this.count++;

}

class GFG {

static final int NO_OF_CHARS = 256;

static HashMap<Character, CountIndex> hm

= new HashMap<Character, CountIndex>(NO_OF_CHARS);

static void getCharCountArray(String str)

{

for (int i = 0; i < str.length(); i++) {

if (hm.containsKey(str.charAt(i))) {

hm.get(str.charAt(i)).incCount();

}

else {

hm.put(str.charAt(i), new CountIndex(i));

}

static int firstNonRepeating(String str)

{

getCharCountArray(str);

int result = Integer.MAX_VALUE, i;

for (Map.Entry<Character, CountIndex> entry : hm.entrySet())

{

int c=entry.getValue().count;

int ind=entry.getValue().index;

if(c==1 && ind < result)

{

result=ind;

}

return result;

}

public static void main(String[] args)

{

String str = "geeksforgeeks";

int index = firstNonRepeating(str);

System.out.println(

index == Integer.MAX_VALUE

? "Either all characters are repeating "

+ " or string is empty"

: "First non-repeating character is "

+ str.charAt(index));

}

Python3

import sys

NO_OF_CHARS = 256

def firstNonRepeating(Str):

arr = [[] for i in range(NO_OF_CHARS)]

for i in range(NO_OF_CHARS):

arr[i] = [0,0]

for i in range(len(Str)):

arr[ord(Str[i])][0] += 1

arr[ord(Str[i])][1]= i

res = sys.maxsize

for i in range(NO_OF_CHARS):

if (arr[i][0] == 1):

res = min(res, arr[i][1])

return res

Str = "geeksforgeeks"

index = firstNonRepeating(Str)

if (index == sys.maxsize):

print("Either all characters are repeating or string is empty")

else:

print("First non-repeating character is ",Str[index])

C#

using System;

using System.Collections.Generic;

class CountIndex {

public int count, index;

public CountIndex(int index)

{

this.count = 1;

this.index = index;

}

public virtual void incCount()

{

this.count++;

}

class GFG {

public const int NO_OF_CHARS = 256;

public static Dictionary<char,

CountIndex>

hm = new Dictionary<char,

CountIndex>(NO_OF_CHARS);

public static void getCharCountArray(string str)

{

for (int i = 0; i < str.Length; i++) {

if (hm.ContainsKey(str[i])) {

hm[str[i]].incCount();

}

else {

hm[str[i]] = new CountIndex(i);

}

internal static int firstNonRepeating(string str)

{

getCharCountArray(str);

int result = int.MaxValue, i;

for (i = 0; i < str.Length; i++) {

if (hm[str[i]].count == 1 && result > hm[str[i]].index) {

result = hm[str[i]].index;

}

return result;

}

public static void Main(string[] args)

{

string str = "geeksforgeeks";

int index = firstNonRepeating(str);

Console.WriteLine(

index == int.MaxValue

? "Either all characters are repeating "

+ " or string is empty"

: "First non-repeating character is "

+ str[index]);

}

Javascript

<script>

const NO_OF_CHARS = 256

function firstNonRepeating(str)

{

let arr = new Array(NO_OF_CHARS)

for(let i=0;i<NO_OF_CHARS;i++){

arr[i] = [0,0];

}

for (let i=0;i<str.length;i++) {

arr[str.charCodeAt(i)][0]++;

arr[str.charCodeAt(i)][1]= i;

}

let res = Number.MAX_VALUE;

for (let i = 0; i < NO_OF_CHARS; i++)

if (arr[i][0] == 1)

res = Math.min(res, arr[i][1]);

return res;

}

let str = "geeksforgeeks";

let index = firstNonRepeating(str);

if (index == Number.MAX_VALUE)

document.write("Either all characters are repeating or string is empty");

else

document.write("First non-repeating character is ",str[index]);

</script>

Output

First non-repeating character is f

Complexity Analysis:

Time Complexity: O(n).
As the string need to be traversed at-least once.
Auxiliary Space: O(1).
Space is occupied by the use of count_array/hash_map to keep track of frequency.

Method #3: Count array and single string traversal:

Approach: Make a count array of maximum number of characters(256). We can initialize all the elements in this array to -1. And then loop through our string character by character and check if the array element with this character as index is -1 or not. If it is -1 then change it to i and if it not -1 then this means that this character already appeared before, so change it to -2.

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.

Implementation:

C++

# include<iostream>

# include<climits>

using namespace std;

int firstNonRepeating(string str) {

int fi[256];

for(int i = 0; i<256; i++)

fi[i] = -1;

for(int i = 0; i<str.length(); i++) {

if(fi[str[i]] == -1) {

fi[str[i]] = i;

}else {

fi[str[i]] = -2;

}

int res = INT_MAX;

for(int i = 0; i<256; i++) {

if(fi[i] >= 0)

res = min(res, fi[i]);

}

if(res == INT_MAX) return -1;

else return res;

}

int main(){

string str;

str = "geeksforgeeks";

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;

}

Java

public class GFG {

public static int firstNonRepeating(String str) {

int[] fi = new int [256];

for(int i = 0; i<256; i++)

fi[i] = -1;

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;

}

int res = Integer.MAX_VALUE;

for(int i = 0; i<256; i++) {

if(fi[i] >= 0)

res = Math.min(res, fi[i]);

}

if(res == Integer.MAX_VALUE) return -1;

else return res;

}

public static void main(String args[]){

String str;

str = "geeksforgeeks";

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));

}

Python3

import sys

def firstNonRepeating(Str):

fi = [-1 for i in range(256)]

for i in range(len(Str)):

if(fi[ord(Str[i])] ==-1):

fi[ord(Str[i])] = i

else:

fi[ord(Str[i])] = -2

res = sys.maxsize

for i in range(256):

if(fi[i] >= 0):

res = min(res, fi[i])

if(res == sys.maxsize):

return -1

else:

return res

Str = "geeksforgeeks"

firstIndex = firstNonRepeating(Str)

if (firstIndex == -1):

print("Either all characters are repeating or string is empty")

else:

print("First non-repeating character is "+ str(Str[firstIndex]))

C#

using System;

public class GFG {

public static int firstNonRepeating(string str)

{

int[] fi

= new int[256];

for (int i = 0; i < 256; i++)

fi[i] = -1;

for (int i = 0; i < str.Length; i++) {

if (fi[str[i]] == -1) {

fi[str[i]] = i;

}

else {

fi[str[i]] = -2;

}

int res = Int32.MaxValue;

for (int i = 0; i < 256; i++) {

if (fi[i] >= 0)

res = Math.Min(res, fi[i]);

}

if (res == Int32.MaxValue)

return -1;

else

return res;

}

public static void Main()

{

string str;

str = "geeksforgeeks";

int firstIndex = firstNonRepeating(str);

if (firstIndex == -1)

Console.WriteLine(

"Either all characters are repeating or string is empty");

else

Console.WriteLine(

"First non-repeating character is "

+ str[firstIndex]);

}

Javascript

<script>

function firstNonRepeating(str)

{

var fi=new Array(256);

fi.fill(-1);

for(var i = 0; i<256; i++)

fi[i] = -1;

for(var i = 0; i<str.length; i++)

{

if(fi[str.charCodeAt(i)] ==-1)

{

fi[str.charCodeAt(i)] = i;

}

else

{

fi[str.charCodeAt(i)] = -2;

}

var res = Infinity;

for(var i = 0; i<256; i++) {

if(fi[i] >= 0)

res = Math.min(res, fi[i]);

}

if(res == Infinity) return -1;

else return res;

}

var str;

str = "geeksforgeeks";

var firstIndex = firstNonRepeating(str);

if (firstIndex === -1)

document.write("Either all characters are repeating or string is empty");

else

document.write("First non-repeating character is "+ str.charAt(firstIndex));

</script>

Output

First non-repeating character is f

Complexity Analysis:

Time Complexity: O(n).
As the string need to be traversed once
Auxiliary Space: O(1).
Space is occupied by the use of count-array to keep track of frequency.

Method #4: Using Built-in Python Functions:

Approach:

Calculate all frequencies of all characters using Counter() function.
Traverse the string and check if any element has frequency 1.
Print the character and break the loop.

Below is the implementation:

Python3

from collections import Counter

def printNonrepeated(string):

freq = Counter(string)

for i in string:

if(freq[i] == 1):

print(i)

break

string = "geeksforgeeks"

printNonrepeated(string)

Time Complexity: O(n). As the string need to be traversed at-least once.
Auxiliary Space: O(n).

Using string function find():

Approach: Search every letter after its current position. should it return -1, it means the letter has just one occurrence that is the current index.

Implementation:

C++

#include<bits/stdc++.h>

using namespace std;

void FirstNonRepeat(string s){

for(int i = 0; i < s.length(); i++)

{

if (s.find(s[i] ,s.find(s[i])+1) == string::npos)

{

cout<<s[i];

break;

}

return;

}

int main(){

string s = "geeksforgeeks";

FirstNonRepeat(s);

}

Python3

def FirstNonRepeat(s):

for i in s:

if (s.find(i,(s.find(i)+1))) == -1:

print(i)

break

return

s = 'geeksforgeeks'

FirstNonRepeat(s)

C#

using System;

public static class GFG

{

public static void FirstNonRepeat(string s)

{

for (int i = 0; i < s.Length; i++) {

if (s.IndexOf(s[i], s.IndexOf(s[i]) + 1)

== -1) {

Console.Write(s[i]);

break;

}

return;

}

internal static void Main()

{

string s = "geeksforgeeks";

FirstNonRepeat(s);

}

Javascript

<script>

function FirstNonRepeat(s){

for(let i = 0; i < s.length; i++)

{

if (s.indexOf(s.charAt(i),s.indexOf(s.charAt(i))+1) == -1)

{

document.write(s[i])

break

}

return

}

let s = 'geeksforgeeks'

FirstNonRepeat(s)

</script>

Time Complexity: O(n^2)
Auxiliary Space: O(1).

Approach : Using count() method.If the count of particular character within the string is 1, then the character is non repeating.After finding the first non repeating character, break the loop and display it.

Python3

string = "geeksforgeeks"

index=-1

fnc=""

for i in string:

if string.count(i) == 1:

fnc+=i

break

else:

index+=1

if index == 1:

print ("Either all characters are repeating or string is empty")

else:

print ("First non-repeating character is" , fnc)

Output

First non-repeating character is f

Time Complexity: O(n)
Auxiliary Space: O(1).

Related Problem: K’th Non-repeating Character
Please suggest if someone has a better solution which is more efficient in terms of space and time.
This article is contributed by Aarti_Rathi. Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

How do you count non

"": slen0 = len(myStr) ch = myStr[0] myStr = myStr. replace(ch, "") slen1 = len(myStr) if slen1 == slen0-1: print ("First non-repeating character = ",ch) break; else: print ("No Unique Character Found! ")