## Description

输入: s = "leetcode"



输入: s = "abc"



• 0 <= len(s) <= 100
• 如果你不使用额外的数据结构，会很加分。

## Solutions

### 0. 问清楚条件

首先应该问下面试官字符串类型，是否只有字母，是什么编码类型，是 ASCII 还是 Unicode。

### 1. 构建 bool 数组

假设字符串是 ASCII 字符串，采用 bool 数组来操作。

# Time: O(n)
# Space: O(1)
class Solution:
def isUnique(self, astr: str) -> bool:
# Assuming character set is ASCII (128 characters)
if len(astr) > 128:
return False
char_set = [False for _ in range(128)]
for char in astr:
val = ord(char)
if char_set[val]:
# Char already found in astr
return False
char_set[val] = True
return True


### 2. Bit Manipulation

# Time: O(n^2)
# Space: O(n)
class Solution:
def isUnique(self, astr: str) -> bool:
n = len(astr)
for i in range(n):
for j in range(i+1, n):
if ord(astr[i]) ^ ord(astr[j]) == 0:
return False
return True


### 3. Bit Manipulation Optimization

假设字符全是字母后，可以这样进行位操作。

variable mark : 0000 0000 0000 0000 0000 0000 0000 0000
mark as       :        zy xwvu tsrq ponm lkji hgfe dcba

# Time: O(n)
# Space: O(1)
class Solution:
def isUnique(self, astr: str) -> bool:
visited = 0
for ch in astr:
if visited & (b := 1 << (ord(ch) - 97)):
return False
visited |= b
return True


### 4. 集合

class Solution:
def isUnique(self, astr: str) -> bool:
return len({*astr}) == len(astr)


### 5. 排序

class Solution:
def isUnique(self, astr: str) -> bool:
s = sorted(astr)
return all(s[i] != c for i, c in enumerate(s[1: ]))