/*
PROBLEM

Given a list of words, we may encode it by writing a reference string S and a list of indexes A.

For example, if the list of words is ["time", "me", "bell"], we can write it as S = "time#bell#" and indexes = [0, 2, 5].

Then for each index, we will recover the word by reading from the reference string from that index until we reach a "#" character.

What is the length of the shortest reference string S possible that encodes the given words?

Example:

Input: words = ["time", "me", "bell"]
Output: 10
Explanation: S = "time#bell#" and indexes = [0, 2, 5].
Note:

1 <= words.length <= 2000.
1 <= words[i].length <= 7.
Each word has only lowercase letters.

*/


// SOLUTION

import "sort"

// trie datastructure
type TrieNode struct {
    Val string
    Children []*TrieNode
}


type byLength []string

func (s byLength) Len() int {
    return len(s)
}

func (s byLength) Swap(i, j int) {
    s[i], s[j] = s[j], s[i]
}

// rig it -- we want the longest words FIRST. so less means whichever is longer length
func (s byLength) Less(i, j int) bool {
    if len(s[i]) > len(s[j]) {
        return true
    }
    return false
}


func minimumLengthEncoding(words []string) int {

    // have to sort words by length
    sort.Sort(byLength(words))
    fmt.Printf("SORTED: %#v\n", words)

    trie := &TrieNode{Val: "", Children: []*TrieNode{}}
    total := 0
    kept := 0
    // construct the suffix tree by working backwards through each string in "words."
    // one character per list node.
    for _, w := range words {
        leaf := add(trie, w)
        if leaf {
            kept += 1
            total += len(w)
            fmt.Printf("%s is a new leaf, adding 1 to kept (now %d), adding %d to total (now %d)\n", w, kept, len(w), total)
        } else {
            fmt.Printf("%s is embedded already\n", w)
        }
    }
    return total + kept
}


/*
when adding, we keep track of if my first letter is a leaf.
if NOT a leaf, return false (I'm folded into the encoding)
if I AM a leaf, return true
*/
//  "" -> e -> m -> i -> t
//     -> l -> l -> e -> b
func add(trie *TrieNode, w string) bool {
    //fmt.Printf("Adding word to trie: %s\n", w)
    if len(w) == 0 {
        return false
    }
    newPath := false
    for i := len(w)-1; i >= 0; i-- {
        found := inChildren(trie, string(w[i]))
        if found == -1 {
            newPath = true
            trie.Children = append(trie.Children, &TrieNode{Val: string(w[i]), Children: []*TrieNode{}})
            trie = trie.Children[len(trie.Children)-1]
        } else {
            trie = trie.Children[found]
        }
    }
    // check if leaf that forged a new path (not a duplicate word)
    if len(trie.Children) == 0 && newPath {
        return true
    }
    return false
}

func inChildren(trie *TrieNode, char string) int {
    if trie == nil {
        return -1
    }
    for i, child := range trie.Children {
        if child.Val == char {
            return i
        }
    }
    return -1
}