Sunday, June 19, 2016

longest substring with 2 unique chars

On 3rd char, reset back to 2nd char's index (first occurrence).

Same code works for 3+ unique chars too.
// example
xx xxxxx
abbcbcbdddde
|-|3 ..   ..
 |----|6  ..
   |--|4  ..
    |-|3  ..
     ||2  ..
      |---|5
       |---|5
(s, k = 2):
    if s == null:
        throw
    maxstart = maxend = 0
    set unique = new
    resetindex = 0
    start = i = 0
    while i < s.length():
        c = s[i]
        if unique.has(c):
            i++
        else if unique.count() == k:
            if i-start > maxend-maxstart:
                maxstart = start, maxend = i
            unique.clear()
            start = i = resetindex
        else:
            unique.add(c)
            // reset from 2nd char's index (first occurrence)
            if unique.count() == 2:
                resetindex = i
            i++
    if i-start > maxend-maxstart:
        maxstart = start, maxend = i
    return s.substring(maxstart, maxend-maxstart)
It's better to use a circular queue and map. The circular queue is useful to drop the oldest char. The map is mainly to hold the index of chars to adjust start.
(s, k = 2)
    startimap = new
    cq = new circularQueue(capacity: k)
    for i = 0, i < s.length(), i++:
        c = s[i]
        if !startimap.hasKey(c):
            if cq.count() == k:
                dropc = cq.dequeue()
                startimap.removeKey(dropc)
                cq.enqueue(c)
                startimap[c] = i
                start = startimap[cq.peek()]
            else: // 0 to k-1
                cq.enqueue(c)
                startimap[c] = i
        else:
            if cq.peekTail() != c:
                cq.enqueue(c)
                startimap[c] = i
        if i-start > maxend-maxstart:
            maxstart = start
            maxend = i
    return (maxstart, maxend)

circularQueue:
    enqueue(x):
    x dequeue():
    x peek():    // return head
    x peekTail(): // return tail
[Hat tip to SM]

No comments:

Post a Comment