## Monday, June 13, 2016

### Longest substring of distinct characters in a stream

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.
``````//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.
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
1. a arrives , maxLenght = 1, map = { a= 0}
2. b arrives maxLenght = 2, map = { a= 0, b = 1}
3. c arrives maxLenght = 3, map = { a= 0, b = 1, c= 2}
4. d arrives maxLenght = 4, map = { a= 0, b = 1, c= 2, d = 3}
5. e arrives maxLenght = 5 map = { a= 0, b = 1, c= 2, d = 3, e = 4}
6. f arrives maxLenght = 6 map = { a= 0, b = 1, c= 2, d = 3, e= 4, f = 5}
7. 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;
}``````