https://discuss.leetcode.com/topic/119/longest-substring-of-distinct-characters-in-a-stream
Return length of the Longest substring of distinct characters from a stream of character.
The stream can be very long and saving the whole stream in memory is not an option.
The stream can be very long and saving the whole stream in memory is not an option.
//following method is used to receive new char from the stream
put(char c)
This is same as the https://leetcode.com/problems/longest-substring-with-at-most-k-distinct-characters/
but the stream makes it a little complicated.
but the stream makes it a little complicated.
I keep in map the last position of each dinstict char in stream. When there is a dublicate char ch, remove from map all chars with positions earlier or equal than last position of ch and reindex the other characters.
Example :
a b c d e f c d k l m n o p f
0 1 2 3 4 5
x x x 0 1 2 3
x x x x 0 1 2 3 4 5 6 7 8 9
x x x x x x 0 1 2 3 4 5 6 7 8 9,
where x - removed character
Example :
a b c d e f c d k l m n o p f
0 1 2 3 4 5
x x x 0 1 2 3
x x x x 0 1 2 3 4 5 6 7 8 9
x x x x x x 0 1 2 3 4 5 6 7 8 9,
where x - removed character
- a arrives , maxLenght = 1, map = { a= 0}
- b arrives maxLenght = 2, map = { a= 0, b = 1}
- c arrives maxLenght = 3, map = { a= 0, b = 1, c= 2}
- d arrives maxLenght = 4, map = { a= 0, b = 1, c= 2, d = 3}
- e arrives maxLenght = 5 map = { a= 0, b = 1, c= 2, d = 3, e = 4}
- f arrives maxLenght = 6 map = { a= 0, b = 1, c= 2, d = 3, e= 4, f = 5}
- c arrives maxLenght = 6 map = {c= 3, d = 0, e= 1, f = 2}
private int maxLength;
private int pos;
private Map<Character,Integer> freq;
public LongestDistinctSubsequence() {
freq = new HashMap<>();
}
public void put(char ch) {
if (!freq.containsKey(ch)) {
freq.put(ch, pos);
pos++;
maxLength = Math.max(pos, maxLength) ;
}
else {
int chPos = freq.get(ch);
Iterator<Entry<Character,Integer>> it = freq.entrySet().iterator();
while (it.hasNext()) {
Entry<Character,Integer> entry = it.next();
if (entry.getValue() <= chPos) {
it.remove();
}
else {
freq.put(entry.getKey(), freq.get(entry.getKey()) - chPos - 1);
}
}
freq.put(ch, pos - chPos - 1);
pos = pos - chPos;
}
}
public int getMaxLength() {
return maxLength;
}