Skip to content

Instantly share code, notes, and snippets.

@manigandand
Last active April 29, 2021 20:23
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save manigandand/26d1d83e692838a52df543640c3eaa54 to your computer and use it in GitHub Desktop.
Save manigandand/26d1d83e692838a52df543640c3eaa54 to your computer and use it in GitHub Desktop.
Maximum common substring multi lang - codesignal test
import (
"strings"
"sort"
)
type meta struct {
count int
matchWords map[string]bool
}
func maxCommonSubstringMultiLang(words []string, k int) string {
// i didn't understand the problem fully/clearly
// There are no strings of length at least four which appear in at least k = 2 words from the given array words. this confusing, on what basis we should split the words
wl := len(words)
if wl == 1 {
return words[0]
}
if wl > 100 {
return ""
}
if k == 0 {
return ""
}
maxLength := 50
maxWordLenErr := false
// split the words by its len and fllowed by len-1,...
splitedWords := make(map[int]map[string]meta)
for i := maxLength; i >= 1; i-- {
splitedWords[i] = make(map[string]meta)
for _, w := range words {
sl := len(w)
if sl > maxLength {
maxWordLenErr = true
continue
}
if sl >= i {
// fmt.Println(w)
for j := 0; j < sl; j++ {
// split only upto j+1 < sl
if j+i <= sl {
// fmt.Printf("%d:%d => %s rem:> %s\n", j, i, w[j:i+j], w)
word := w[j:i+j]
wmeta, ok := splitedWords[i][word]
if !ok {
splitedWords[i][word] = meta{
count: 1,
matchWords: map[string]bool{
w: true,
},
}
continue
}
wmeta.count = wmeta.count + 1
wmeta.matchWords[w] = true
splitedWords[i][word] = wmeta
}
}
}
}
}
if maxWordLenErr {
return ""
}
var (
result []string
resultM = make(map[string]meta)
)
for i := maxLength; i >= 1; i-- {
wordCounts := splitedWords[i]
for w, meta := range wordCounts{
if len(meta.matchWords) >= k {
// fmt.Println(i, "> ", w, " => ", meta)
result = append(result, w)
resultM[w] = meta
}
}
if len(result) > 0 {
break
}
}
if len(result) == 1 {
return result[0]
}
sort.Strings(result)
// check Lexicographical Order
var res string
for i := range result {
if i+1 != len(result) {
// 0 index
if i == 0 {
if lexVal := strings.Compare(result[i], result[i+1]); lexVal == -1 {
// fmt.Println(i, result[i], result[i+1], lexVal)
res = result[i]
continue
}
}
// TODO: check only if the count is greater than the res
if lexVal := strings.Compare(res, result[i+1]); lexVal == -1 {
// fmt.Println(i, res, result[i+1], lexVal)
res = result[i+1]
continue
}
}
}
return result[0]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment