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, uniqueCharCount = 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() == uniqueCharCount:
            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)
[Hat tip to SM]

No comments:

Post a Comment