Given a string, determine if the string has all unique characters.
Examples :
Input : abcd10jk
Output : true
Input : hutg9mnd!nk9
Output : false
Approach 1 – Brute Force technique: Run 2 loops with variable i and j. Compare str[i] and str[j]. If they become equal at any point, return false.
C++
#include <bits/stdc++.h>
using namespace std;
bool uniqueCharacters(string str)
{
for (int i = 0; i < str.length() - 1; i++) {
for (int j = i + 1; j < str.length(); j++) {
if (str[i] == str[j]) {
return false;
}
}
}
return true;
}
int main()
{
string str = "neveropen";
if (uniqueCharacters(str)) {
cout << "The String " << str
<< " has all unique characters\n";
}
else {
cout << "The String " << str
<< " has duplicate characters\n";
}
return 0;
}
|
Java
import java.util.*;
class GfG {
boolean uniqueCharacters(String str)
{
for (int i = 0; i < str.length(); i++)
for (int j = i + 1; j < str.length(); j++)
if (str.charAt(i) == str.charAt(j))
return false;
return true;
}
public static void main(String args[])
{
GfG obj = new GfG();
String input = "neveropen";
if (obj.uniqueCharacters(input))
System.out.println("The String " + input + " has all unique characters");
else
System.out.println("The String " + input + " has duplicate characters");
}
}
|
Python3
def uniqueCharacters(str):
for i in range(len(str)):
for j in range(i + 1,len(str)):
if(str[i] == str[j]):
return False;
return True;
str = "neveropen";
if(uniqueCharacters(str)):
print("The String ", str," has all unique characters");
else:
print("The String ", str, " has duplicate characters");
|
C#
using System;
public class GFG {
static bool uniqueCharacters(String str)
{
for (int i = 0; i < str.Length; i++)
for (int j = i + 1; j < str.Length; j++)
if (str[i] == str[j])
return false;
return true;
}
public static void Main()
{
string input = "neveropen";
if (uniqueCharacters(input) == true)
Console.WriteLine("The String " + input
+ " has all unique characters");
else
Console.WriteLine("The String " + input
+ " has duplicate characters");
}
}
|
PHP
<?php
function uniqueCharacters($str)
{
for($i = 0; $i < strlen($str); $i++)
{
for($j = $i + 1; $j < strlen($str); $j++)
{
if($str[$i] == $str[$j])
{
return false;
}
}
}
return true;
}
$str = "neveropen";
if(uniqueCharacters($str))
{
echo "The String ", $str,
" has all unique characters\n";
}
else
{
echo "The String ", $str,
" has duplicate characters\n";
}
?>
|
Javascript
<script>
function uniqueCharacters(str)
{
for(let i = 0; i < str.length; i++)
for(let j = i + 1; j < str.length; j++)
if (str[i] == str[j])
return false;
return true;
}
let input = "neveropen";
if (uniqueCharacters(input) == true)
document.write("The String " + input +
" has all unique characters" + "</br>");
else
document.write("The String " + input +
" has duplicate characters");
</script>
|
Output :
The String neveropen has duplicate characters
Time Complexity: O(n2)
Auxiliary Space: O(1)
Note: Please note that the program is case-sensitive.
Approach 2 – Sorting: Using sorting based on ASCII values of characters
C++
#include <bits/stdc++.h>
using namespace std;
bool uniqueCharacters(string str)
{
sort(str.begin(), str.end());
for (int i = 0; i < str.length()-1; i++) {
if (str[i] == str[i + 1]) {
return false;
}
}
return true;
}
int main()
{
string str = "neveropen";
if (uniqueCharacters(str)) {
cout << "The String " << str
<< " has all unique characters\n";
}
else {
cout << "The String " << str
<< " has duplicate characters\n";
}
return 0;
}
|
Java
import java.util.*;
class GfG {
boolean uniqueCharacters(String str)
{
char[] chArray = str.toCharArray();
Arrays.sort(chArray);
for (int i = 0; i < chArray.length - 1; i++) {
if (chArray[i] != chArray[i + 1])
continue;
else
return false;
}
return true;
}
public static void main(String args[])
{
GfG obj = new GfG();
String input = "neveropen";
if (obj.uniqueCharacters(input))
System.out.println("The String " + input
+ " has all unique characters");
else
System.out.println("The String " + input
+ " has duplicate characters");
}
}
|
Python3
def uniqueCharacters(st):
st = sorted(st)
for i in range(len(st)-1):
if (st[i] == st[i + 1]) :
return False
return True
if __name__=='__main__':
st = "neveropen"
if (uniqueCharacters(st)) :
print("The String",st,"has all unique characters\n")
else :
print("The String",st,"has duplicate characters\n")
|
C#
using System;
public class GFG {
static bool uniqueCharacters(String str)
{
char[] chArray = str.ToCharArray();
Array.Sort(chArray);
for (int i = 0; i < chArray.Length - 1; i++) {
if (chArray[i] != chArray[i + 1])
continue;
else
return false;
}
return true;
}
public static void Main()
{
string input = "neveropen";
if (uniqueCharacters(input) == true)
Console.WriteLine("The String " + input
+ " has all unique characters");
else
Console.WriteLine("The String " + input
+ " has duplicate characters");
}
}
|
Javascript
<script>
function uniqueCharacters(str)
{
let chArray = str.split('');
chArray.sort();
for (let i = 0; i < chArray.length - 1; i++)
{
if (chArray[i] != chArray[i + 1])
continue;
else
return false;
}
return true;
}
let input = "neveropen";
if (uniqueCharacters(input) == true)
document.write("The String " + input +
" has all unique characters" + "</br>");
else
document.write("The String " + input +
" has duplicate characters" + "</br>");
</script>
|
Output:
The String neveropen has duplicate characters
Time Complexity: O(nlogn)
Auxiliary Space: O(1)
Approach 3 – Use of Extra Data Structure: This approach assumes ASCII char set(8 bits). The idea is to maintain a boolean array for the characters. The 256 indices represent 256 characters. All the array elements are initially set to false. As we iterate over the string, set true at the index equal to the int value of the character. If at any time, we encounter that the array value is already true, it means the character with that int value is repeated.
C++
#include <cstring>
#include <iostream>
using namespace std;
const int MAX_CHAR = 256;
bool uniqueCharacters(string str)
{
if (str.length() > MAX_CHAR)
return false;
bool chars[MAX_CHAR] = { 0 };
for (int i = 0; i < str.length(); i++) {
if (chars[int(str[i])] == true)
return false;
chars[int(str[i])] = true;
}
return true;
}
int main()
{
string str = "neveropen";
if (uniqueCharacters(str)) {
cout << "The String " << str
<< " has all unique characters\n";
}
else {
cout << "The String " << str
<< " has duplicate characters\n";
}
return 0;
}
|
Java
import java.util.*;
class GfG {
int MAX_CHAR = 256;
boolean uniqueCharacters(String str)
{
if (str.length() > MAX_CHAR)
return false;
boolean[] chars = new boolean[MAX_CHAR];
Arrays.fill(chars, false);
for (int i = 0; i < str.length(); i++) {
int index = (int)str.charAt(i);
if (chars[index] == true)
return false;
chars[index] = true;
}
return true;
}
public static void main(String args[])
{
GfG obj = new GfG();
String input = "neveropen";
if (obj.uniqueCharacters(input))
System.out.println("The String " + input
+ " has all unique characters");
else
System.out.println("The String " + input
+ " has duplicate characters");
}
}
|
Python3
MAX_CHAR = 256;
def uniqueCharacters(string):
n = len(string)
if n > MAX_CHAR:
return False
chars = [False] * MAX_CHAR
for i in range(n):
index = ord(string[i])
if (chars[index] == True):
return False
chars[index] = True
return True
if __name__ == '__main__':
input = "neveropen"
if (uniqueCharacters(input)):
print("The String", input,
"has all unique characters")
else:
print("The String", input,
"has duplicate characters")
|
C#
using System;
class GfG {
static int MAX_CHAR = 256;
bool uniqueCharacters(String str)
{
if (str.Length > MAX_CHAR)
return false;
bool[] chars = new bool[MAX_CHAR];
for (int i = 0; i < MAX_CHAR; i++) {
chars[i] = false;
}
for (int i = 0; i < str.Length; i++) {
int index = (int)str[i];
if (chars[index] == true)
return false;
chars[index] = true;
}
return true;
}
public static void Main(String[] args)
{
GfG obj = new GfG();
String input = "neveropen";
if (obj.uniqueCharacters(input))
Console.WriteLine("The String " + input
+ " has all unique characters");
else
Console.WriteLine("The String " + input
+ " has duplicate characters");
}
}
|
Javascript
<script>
let MAX_CHAR = 256;
function uniqueCharacters(str)
{
if (str.length > MAX_CHAR)
return false;
let chars = new Array(MAX_CHAR);
for (let i = 0; i < MAX_CHAR; i++) {
chars[i] = false;
}
for (let i = 0; i < str.length; i++) {
let index = str[i].charCodeAt();
if (chars[index] == true)
return false;
chars[index] = true;
}
return true;
}
let input = "neveropen";
if (uniqueCharacters(input))
document.write("The String " + input
+ " has all unique characters");
else
document.write("The String " + input
+ " has duplicate characters");
</script>
|
Output:
The String neveropen has duplicate characters
Time Complexity: O(n)
Auxiliary Space: O(n)
Approach 4 – Without Extra Data Structure: The approach is valid for strings having alphabet as a-z. This approach is a little tricky. Instead of maintaining a boolean array, we maintain an integer value called checker(32 bits). As we iterate over the string, we find the int value of the character with respect to ‘a’ with the statement int bitAtIndex = str.charAt(i)-‘a’;
Then the bit at that int value is set to 1 with the statement 1 << bitAtIndex .
Now, if this bit is already set in the checker, the bit AND operation would make the checker > 0. Return false in this case.
Else Update checker to make the bit 1 at that index with the statement checker = checker | (1 <<bitAtIndex);
C++
#include <bits/stdc++.h>
using namespace std;
bool uniqueCharacters(string str)
{
int checker = 0;
for (int i = 0; i < str.length(); i++) {
int bitAtIndex = str[i] - 'a';
if ((checker & (1 << bitAtIndex)) > 0) {
return false;
}
checker = checker | (1 << bitAtIndex);
}
return true;
}
int main()
{
string str = "neveropen";
if (uniqueCharacters(str)) {
cout << "The String " << str
<< " has all unique characters\n";
}
else {
cout << "The String " << str
<< " has duplicate characters\n";
}
return 0;
}
|
Java
import java.util.*;
class GfG {
boolean uniqueCharacters(String str)
{
int checker = 0;
for (int i = 0; i < str.length(); i++) {
int bitAtIndex = str.charAt(i) - 'a';
if ((checker & (1 << bitAtIndex)) > 0)
return false;
checker = checker | (1 << bitAtIndex);
}
return true;
}
public static void main(String args[])
{
GfG obj = new GfG();
String input = "geekforneveropen";
if (obj.uniqueCharacters(input))
System.out.println("The String " + input
+ " has all unique characters");
else
System.out.println("The String " + input
+ " has duplicate characters");
}
}
|
Python3
import math
def uniqueCharacters(string):
checker = 0
for i in range(len(string)):
bitAtIndex = ord(string[i]) - ord('a')
if ((bitAtIndex) > 0):
if ((checker & ((1 << bitAtIndex))) > 0):
return False
checker = checker | (1 << bitAtIndex)
return True
if __name__ == '__main__':
input = "geekforneveropen"
if (uniqueCharacters(input)):
print("The String " + input +
" has all unique characters")
else:
print("The String " + input +
" has duplicate characters")
|
C#
using System;
class GFG {
public virtual bool uniqueCharacters(string str)
{
int checker = 0;
for (int i = 0; i < str.Length; i++) {
int bitAtIndex = str[i] - 'a';
if ((checker & (1 << bitAtIndex)) > 0) {
return false;
}
checker = checker | (1 << bitAtIndex);
}
return true;
}
public static void Main(string[] args)
{
GFG obj = new GFG();
string input = "geekforneveropen";
if (obj.uniqueCharacters(input)) {
Console.WriteLine("The String " + input + " has all unique characters");
}
else {
Console.WriteLine("The String " + input + " has duplicate characters");
}
}
}
|
PHP
<?php
function uniqueCharacters($str)
{
$checker = 0;
for ($i = 0; $i < strlen($str); $i++)
{
$bitAtIndex = $str[$i] - 'a';
if (($checker &
(1 << $bitAtIndex)) > 0)
{
return false;
}
$checker = $checker |
(1 << $bitAtIndex);
}
return true;
}
$str = "neveropen";
if(uniqueCharacters($str))
{
echo "The String ", $str,
" has all unique characters\n";
}
else
{
echo "The String ", $str,
" has duplicate characters\n";
}
?>
|
Javascript
<script>
function uniqueCharacters(str)
{
let checker = 0;
for (let i = 0; i < str.length; i++) {
let bitAtIndex = str[i].charCodeAt(0) - 'a'.charCodeAt(0);
if ((checker & (1 << bitAtIndex)) > 0) {
return false;
}
checker = checker | (1 << bitAtIndex);
}
return true;
}
let input = "geekforneveropen";
if (uniqueCharacters(input)) {
document.write("The String " + input + " has all unique characters");
}
else {
document.write("The String " + input + " has duplicate characters");
}
</script>
|
Output :
The String GeekforGeeks has duplicate characters
Time Complexity: O(n)
Auxiliary Space: O(1)
Exercise: Above program is case insensitive, you can try making the same program that is case sensitive i.e Geeks and GEeks both give different output.
Using Java Stream :
C++
#include <bits/stdc++.h>
using namespace std;
bool uniqueCharacters(string s)
{
for (int i = 0; i < s.size(); i++) {
for (int j = i + 1; j < s.size(); j++) {
if (s[i] == s[j]) {
return false;
}
}
}
return true;
}
int main()
{
string input = "neveropen";
if (uniqueCharacters(input))
cout << "The String " << input
<< " has all unique characters\n";
else
cout << "The String " << input
<< " has duplicate characters\n";
return 0;
}
|
Java
import java.util.Collections;
import java.util.stream.Collectors;
class GfG {
boolean uniqueCharacters(String s)
{
return s.chars().filter(e-> Collections.frequency(s.chars().boxed().collect(Collectors.toList()), e) > 1).count() > 1 ? false: true;
}
public static void main(String args[])
{
GfG obj = new GfG();
String input = "neveropen";
if (obj.uniqueCharacters(input))
System.out.println("The String " + input + " has all unique characters");
else
System.out.println("The String " + input + " has duplicate characters");
}
}
|
Python3
from collections import Counter
def uniqueCharacters(s):
return not any(filter(lambda x: x > 1, list(Counter(list(s)).values())))
input = "neveropen"
if uniqueCharacters(input):
print("The String " + input + " has all unique characters")
else:
print("The String " + input + " has duplicate characters")
|
C#
using System.Linq;
class GfG {
public bool UniqueCharacters(string s) {
return s.ToCharArray().Count(e => s.Count(f => f == e) > 1) > 1 ? false : true;
}
static void Main(string[] args) {
GfG obj = new GfG();
string input = "neveropen";
if (obj.UniqueCharacters(input))
System.Console.WriteLine("The String " + input + " has all unique characters");
else
System.Console.WriteLine("The String " + input + " has duplicate characters");
}
}
|
Javascript
function uniqueCharacters(s)
{
let arr = s.split("");
return !arr.some((v, i) => arr.indexOf(v) < i);
}
let input = "neveropen";
if (uniqueCharacters(input))
console.log("The String " + input + " has all unique characters");
else
console.log("The String " + input + " has duplicate characters");
|
Reference:
Cracking the Coding Interview by Gayle
Approach 5: Using sets() function:
- Convert the string to set.
- If the length of set is equal to the length of the string then return True else False.
Below is the implementation of the above approach
C++
#include <bits/stdc++.h>
using namespace std;
bool uniqueCharacters(string str)
{
set<char> char_set;
for(char c : str)
{
char_set.insert(c);
}
return char_set.size() == str.size();
}
int main()
{
string str = "neveropen";
if (uniqueCharacters(str))
{
cout << "The String " << str
<< " has all unique characters\n";
}
else
{
cout << "The String " << str
<< " has duplicate characters\n";
}
return 0;
}
|
Java
import java.util.*;
class GFG{
static boolean uniqueCharacters(String str)
{
HashSet<Character> char_set = new HashSet<>();
for(int c = 0; c< str.length();c++)
{
char_set.add(str.charAt(c));
}
return char_set.size() == str.length();
}
public static void main(String[] args)
{
String str = "neveropen";
if (uniqueCharacters(str))
{
System.out.print("The String " + str
+ " has all unique characters\n");
}
else
{
System.out.print("The String " + str
+ " has duplicate characters\n");
}
}
}
|
Python3
def uniqueCharacters(str):
setstring = set(str)
if(len(setstring) == len(str)):
return True
return False
if __name__ == '__main__':
input = "neveropen"
if (uniqueCharacters(input)):
print("The String " + input +
" has all unique characters")
else:
print("The String " + input +
" has duplicate characters")
|
C#
using System;
using System.Collections.Generic;
public class GFG {
static bool uniquechars(String str)
{
HashSet<char> char_set = new HashSet<char>();
for (int c = 0; c < str.Length; c++) {
char_set.Add(str);
}
if (char_set.Count == str.Length) {
return true;
}
else {
return false;
}
}
public static void Main(String[] args)
{
String str = "neveropen";
if (uniquechars(str)) {
Console.Write("The String " + str
+ " has all unique characters\n");
}
else {
Console.Write("The String " + str
+ " has duplicate characters\n");
}
}
}
|
Javascript
<script>
function uniqueCharacters(str)
{
var setstring = new Set(str)
if (setstring.size == str.length)
{
return true
}
else
{
return false
}
}
var input = "neveropen"
if (uniqueCharacters(input))
{
document.write("The String " + input +
" has all unique characters") ;
}
else
{
document.write("The String " + input +
" has duplicate characters")
}
</script>
|
Output:
The String neveropen has duplicate characters
Time Complexity: O(nlogn)
Auxiliary Space: O(n)
This article is contributed by Saloni Baweja. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to contribute@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
