01.01. Is Unique

Description

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

Example 1:


Input:  = "leetcode"

Output: false

Example 2:


Input: s = "abc"

Output: true

Note:

0 <= len(s) <= 100

Solutions

Solution 1: Bit Manipulation

Based on the examples, we can assume that the string only contains lowercase letters (which is confirmed by actual verification).

Therefore, we can use each bit of a $32$-bit integer mask to represent whether each character in the string has appeared.

The time complexity is $O(n)$, where $n$ is the length of the string. The space complexity is $O(1)$.

Python3JavaC++GoTypeScriptJavaScriptSwift

class Solution:
    def isUnique(self, astr: str) -> bool:
        mask = 0
        for c in astr:
            i = ord(c) - ord('a')
            if (mask >> i) & 1:
                return False
            mask |= 1 << i
        return True

class Solution {
    public boolean isUnique(String astr) {
        int mask = 0;
        for (char c : astr.toCharArray()) {
            int i = c - 'a';
            if (((mask >> i) & 1) == 1) {
                return false;
            }
            mask |= 1 << i;
        }
        return true;
    }
}