Amazon Interview Question
SDE1sCountry: United States
This solution takes O(1) space - BitSet and result StringBuilder:
public class RedundantCharacters {
public static void main(String[] args) {
new RedundantCharacters().solve();
}
public void solve() {
String s = "qwertyasdfghytrewq";
System.out.print(removeRedundant(s));
}
public String removeRedundant(String s) {
StringBuilder sb = new StringBuilder();
BitSet bitSet = new BitSet();
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
if (!bitSet.get(ch)) {
sb.append(ch);
}
bitSet.set(ch);
}
return sb.toString();
}
}
Using bit set is O(n) and not O(1) space complexity. Bitset is nothing but array of bits internally.
As far as i see, there needs to be a tradeoff between space and time complexity. Best is [Time complexity vs Space complexity] = [O(n) vs O(n)] or [O(nlogn) vs O(1)]
- Anonymous January 06, 2014