This post is completed by 1 user

  • 0
Add to List
Beginner

11. Check If String has All Unique Characters

Objective: Write an algorithm to find out whether in a given string contains all the unique characters.

Input: A String
Output: True or false based upon whether string contains all the unique characters or not.
Example:
Input: software engineer
Output: false

Input: software
Output: true

Approach:

We will discuss two approaches to solve this problem

Method 1. When characters are not ASCII but could be anything alphabets or special characters

  • Create a boolean array of size 256, and put false at every index.
  • Navigate the input string one character at a time, say 'char a'
  • Check array position of array[a], if it is false, make it true.
  • If it is already true, return false.
  • Time Complexity: O(n), Space Complexity: O(1)

Method 2:

  • Sort the array and do the linear scan to find out whether string contains unique elements or not
  • Time Complexity : O(nlogn), Space Complexity : O(n)

Output

software engineer (Method 1) :false
software engineer (Method 2) :false
software (Method 1) :true
software (Method 2) :true