Problem: Given a string, print non-repeating characters of the string.
Examples:
Example 1: Input: string = “google” Output: l,e Explanation: Non repeating characters are l,e. Example 2: Input: string = “yahoo” Output: y,a,h Explanation: Non repeating characters are y,a,h
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Solution1: Naive Approach
Intuition:
- We will create an array of frequency to store occurrences of each character.
- Now, we will iterate through the string and pick up each character.
- Suppose we selected the character ‘x’, now we will iterate into the string checking the ‘x’ character. If we encounter ‘x’ character, we will increment the count of ‘x’ character in the frequency array
- Same we will be doing for each character in the string.
Approach:
- We will define frequency array.
- We will be using 2 loops. The outer loop we will be used to select a character let’s say ‘x’ and initialize ‘x’ at the corresponding index in the frequency array with +1.
- In the inner loop, we will compare the ‘x’ character with the rest of the characters of the string.
- If we found ‘x’, we will again increment the frequency of ‘x’ by +1 and set the ‘x’ character as ‘-‘ to make it a visited character.
- Finally we will print the character whose frequency is equal to 1 and we will ignore the spaces in the string ( as it is not considered as a character ) and also ‘-‘ to avoid repetition of character.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void nonRepeating(string & st, int freq[200]) {
int i, j;
int l = st.length();
for (int i = 0; i < l; i++) {
freq[i] = 1;
for (int j = i + 1; j < l; j++) {
if (st[i] == st[j]) {
freq[i]++;
st[j] = '-'; // set st[j] to - to avoid visited character
}
}
}
for (int i = 0; i < l; ++i) {
if (freq[i] == 1 && st[i] != ' ' && st[i] != '-') {
cout << st[i] << " ";
}
}
}
};
int main() {
string st = "Takeuforward";
int l = st.length();
int freq[200] = {
0
};
Solution obj;
cout << "Non-repeative character:" << "\n";
obj.nonRepeating(st, freq);
return 0;
}Output:
Non-repeative character:
T k e u f o w d
Time complexity: O(n^2)
Reason: For each character, we are iterating the entire string to count its occurrence.
Space complexity: O(n)
Reason: We are using an array to store the frequency of each character
Java Code
import java.util.*;
public class Solution {
static void nonRepeating(String st, int n) {
int freq[] = new int[200];
char s[] = st.toCharArray();
for (int i = 0; i < n; i++) {
freq[i] = 1;
for (int j = i + 1; j < n; j++) {
if (s[i] == s[j]) {
freq[i]++;
s[j] = '-'; // set s[j] to 0 to avoid printing visited character
}
}
}
for (int i = 0; i < n; ++i) {
if (freq[i] == 1 && s[i] != ' ' && s[i] != '-') {
System.out.print(s[i] + " ");
}
}
}
public static void main(String[] args) {
String st = "blockchain technology";
int n = st.length();
System.out.println("Non-repeative character: ");
nonRepeating(st, n);
}
}Output:
Non-repeative character:
T k e u f o w d
Time complexity: O(n^2)
Reason: For each character, we are iterating the entire string to count its occurrence.
Space complexity: O(n)
Reason: We are using an array to store the frequency of each character
Solution2: Linear Approach
Intuition :
- We will create an array where we will store occurrences of each character. Then iterating through the string we will increment the count of that particular character in the frequency array.
- While iterating if we encounter a space (‘ ‘) we will skip it because it is not considered a character.
Approach:
- We will create an integer array freq.
- Using a for loop we will iterate through the string and increment each character’s occurrence
- At last we print only those characters whose frequency is 1.
This is how the frequency array looks after getting all the occurrences of the character. The red alphabet denotes each index of the integer array. Eg: the value of freq[0] means the count of ‘a’, similarly freq[1] means the count of ‘b’, ….. freq[25] means the count of ‘z’.
Code:
C++ Code
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void nonRepeating(string & st, int freq[200]) {
int i, j;
int l = st.length();
for (int i = 0; i < l; i++) {
if (st[i] == ' ') // ignoring the space in the string
continue;
else
freq[st[i] - 'a']++; // incrementing each character's frequency
}
// Printing non-repeating characters of the string
for (int i = 0; i < l; i++) {
if (freq[st[i] - 'a'] == 1 && st[i] != ' ') {
cout << st[i] << " ";
}
}
}
};
int main() {
string st = "take u forward";
int l = st.length();
int freq[200] = {
0
};
Solution obj;
cout << "Non-Repeating characters: ";
obj.nonRepeating(st, freq);
return 0;
}Output:
Non-Repeating characters: t k e u f o w d
Time complexity: O(n)
Reason: We make a single iteration to fill up the frequency array
Space complexity: O(n)
Reason: We are using an array to store the frequency of each character.
Java Code
import java.util.*;
public class Solution {
static void printFrequency(String st, int n) {
int freq[] = new int[200];
char s[] = st.toCharArray();
for (int i = 0; i < n; i++) {
if (st.charAt(i) == ' ') // ignoring the space in the string
continue;
else
freq[(int) st.charAt(i)]++;//incrementing each character's frequency
}
// Printing the frequency of the string
for (int i = 0; i < n; i++) {
if (freq[(int) st.charAt(i)] == 1 && s[i] != ' ') {
System.out.print(s[i] + " ");
}
}
}
public static void main(String[] args) {
String st = "take u forward";
int n = st.length();
System.out.print("Non-Repeating characters: ");
printFrequency(st, n);
}
}Output:
Non-Repeating characters: t k e u f o w d
Time complexity: O(n)
Reason: We make a single iteration to fill up the frequency array
Space complexity: O(n)
Reason: We are using an array to store the frequency of each character.
Special thanks to Shreyas Vishwakarma for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article