# All Unique

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

### Clarification questions

1. Do whitespace characters count as valid characters, that is if there are two spaces in the string, will the result be false?
2. Does capitalization (or any capital letters) matter?

### Solution 1

Complexity: $T = O(n), S = O(n)$

This solution uses a hash table to store all the characters in the string – if the character already in the table, it returns false

Note: This solution is based on the assumption that hash table access is constant!

### Solution 2

Complexity: $T = O(n\log{n}), S = O(1)$

If space is more important, and we don’t care if the original array is modified or not, we can sort the string inplace, and just iterate through it in linear time.

Note: The assumption here is that either the string is mutable, or the input is not a string but array of characters.

### Solution 3

Complexity: $T = O(n^2), S = O(1)$

If we are not allowed to modify the original array, and the space is more important, we can just compare every character to every other character.

### Zafar

I am a 5th year PhD student at Boston University, working towards my degree in Computer Engineering. While my work focuses on digital design,error mitigation, and machine learning, my non-work interests range widely from information theory (go Shannon!), quantum computing, grandfather paradox, Star Trek, Little Mermaid, 'why is the grass green?', 1Q84, etc., etc., etc. If you want to talk about, well, anything - just ping me.

### String Compression

Implement a method to perform string compression using the counts of repeated characters. If the "compressed" string would not become sma...… Continue reading

#### %20fy the string

Published on December 01, 2016

#### String Permuations

Published on December 01, 2016