Conditional Substring Matching

Given m unique characters [a, b, c, d], and a string “tbcacbdata” of length n. Find a continuous substring s of “tbcacbdata” with length m, such that s only consists of all the characters in m, the order does not matter. Return any of the satisfied substring and the starting position of that substring, return -1 and an empty string if it is not found. For example, in the above example, one should return 3, “acbd”.

package main

import "fmt"

func main(){
    printOutput(find([]byte{'a','b','d'}, []byte{'t','b','c','a','c','b','d','a','t','a'}))

    printOutput(find([]byte{'a','b','d', 'c'}, []byte{'t','b','c','a','c','b','d','a','t','a'}))

    printOutput(find([]byte{'t','b','c'}, []byte{'t','b','c','a','c','b','d','a','t','a'}))

    printOutput(find([]byte{'t'}, []byte{'t','b','c','a','c','b','d','a','t','a'}))

    printOutput(find([]byte{'c','b','a'}, []byte{'t','b','c','a','c','b','d','a','t','a'}))

    printOutput(find([]byte{'t','a'}, []byte{'t','b','c','a','c','b','d','a','t','a'}))

    printOutput(find([]byte{'g'}, []byte{'t','b','c','a','c','b','d','a','t','a'}))
}

func find(a, b []byte) (int, string) {
    mapping := map[byte]bool{}
    // init
    for _, n := range a {
        mapping[n] = true
    }
    i := 0 // Sliding Window left
    for j := 0; j < len(b); j++ { // Sliding Window right
        v, ok := mapping[b[j]] // expand the window to the right
        if ok && v{ // if current character is in m has not yet been used
            // expand the window toward right untill reached the target size
            mapping[b[j]] = false // mark as used
            if j - i + 1 == len(a) { // exit condition: the window has the same size as m
                return i, string(b[i: j + 1])
            }
        } else if ok && !v { // if current character is in m and has been used, such as "cac"
            // update the left side of the winow: to the next of the position of the last appearance of current characters
            if _, okk := mapping[b[i]]; okk {
                for i <= j {
                    if b[i] != b[j]  {
                        mapping[b[i]] = true
                        i++
                    } else {
                        break
                    }
                }
                i++
            }
        } else { // if current character is NOT in m
            // update the left side of the window to the position of window right, and mark everything bEFORE the window right as unused
            for i <= j {
                if _, okk := mapping[b[i]]; okk {
                    mapping[b[i]] = true
                }
                i++
            }
        }
    }
    return -1, ""
}

func printOutput(pos int, str string){
    if pos == -1 {
        fmt.Printf("string not found\n")
    } else {
        fmt.Printf("start at pos: %d, string is: %s\n", pos, str)
    }
}