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

Thinking

A hash set of seen characters decides uniqueness in one scan, in \(O(n)\) time and space proportional to the alphabet. The constraint \(n \le 100\) allows that, but the follow-up asks for no extra data structure.

If the string contains only lowercase letters, there are at most \(26\) symbols, so each bit of an integer can record whether a letter has appeared. On character \(c\), test the corresponding bit: if it is already \(1\), a duplicate exists; otherwise set the bit.

Bit operations turn membership tests and inserts into constant-time, constant-space work, which is why a mask is used instead of a hash table or boolean array.

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 i in map(lambda c: ord(c) - ord("a"), astr):
            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;
    }
}

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

func isUnique(astr string) bool {
    mask := 0
    for _, c := range astr {
        i := c - 'a'
        if mask>>i&1 == 1 {
            return false
        }
        mask |= 1 << i
    }
    return true
}

function isUnique(astr: string): boolean {
    let mask = 0;
    for (let j = 0; j < astr.length; ++j) {
        const i = astr.charCodeAt(j) - 'a'.charCodeAt(0);
        if ((mask >> i) & 1) {
            return false;
        }
        mask |= 1 << i;
    }
    return true;
}

/**
 * @param {string} astr
 * @return {boolean}
 */
var isUnique = function (astr) {
    let mask = 0;
    for (const c of astr) {
        const i = c.charCodeAt() - 'a'.charCodeAt();
        if ((mask >> i) & 1) {
            return false;
        }
        mask |= 1 << i;
    }
    return true;
};

class Solution {
    func isUnique(_ astr: String) -> Bool {
        var mask = 0
        for c in astr {
            let i = Int(c.asciiValue! - Character("a").asciiValue!)
            if (mask >> i) & 1 != 0 {
                return false
            }
            mask |= 1 << i
        }
        return true
    }
}

01.01. Is Unique

Description

Solutions

Solution 1: Bit Manipulation

Comments