Wednesday, June 12, 2013

How to Solve the Longest Substring Problem

Find the longest sub-string of the given string that contains, at most, two unique characters. If you find multiple sub-strings that match the description, print the last sub-string (furthest to the right).

Inputs:

abbccc
abcabcabcabccc
qwertyytrewq
aaabaaabccbcccbde
abcde
aaaa
aabb
Outputs:
bbccc
bccc
tyyt
bccbcccb
de
aaaa
aabb
package main

import (
    "fmt"
)

type Substring struct {
    begin int
    end   int
}

func longestSubstring(str string) string {
    m := map[uint8]bool{}
    substrings := []Substring{}
    for i := 0; i < len(str); i++ {
        if _, ok := m[str[i]]; !ok {
            m[str[i]] = true
        }
        if len(m) == 3 {
            m = map[uint8]bool{}
            m[str[i-1]] = true
            m[str[i]] = true
            if len(substrings) == 0 {
                substrings = append(substrings, Substring{0, i - 1})
            } else {
                begin := substrings[len(substrings)-1].end
                c := str[begin]
                for j := begin; str[j] == c && j != 0; j-- {
                    begin--
                }
                substrings = append(substrings, Substring{begin + 1, i - 1})
            }
        }
    }
    if len(m) == 2 {
        if len(substrings) == 0 {
            substrings = append(substrings, Substring{0, len(str) - 1})
        } else {
            begin := substrings[len(substrings)-1].end
            c := str[begin]
            for j := begin; str[j] == c && j != 0; j-- {
                begin--
            }
            substrings = append(substrings, Substring{begin + 1, len(str) - 1})
        }
    } else {
        return str
    }
    var longest string
    for _, v := range substrings {
        substring := str[v.begin : v.end+1]
        if len(longest) <= len(substring) {
            longest = substring
        }
    }
    return longest
}

func main() {
    fmt.Println(longestSubstring("abbccc"))
    fmt.Println(longestSubstring("abcabcabcabccc"))
    fmt.Println(longestSubstring("qwertyytrewq"))
    fmt.Println(longestSubstring("aaabaaabccbcccbde"))
    fmt.Println(longestSubstring("abcde"))
    fmt.Println(longestSubstring("aaaa"))
    fmt.Println(longestSubstring("aabb"))
}