Last active
April 29, 2021 20:23
-
-
Save manigandand/26d1d83e692838a52df543640c3eaa54 to your computer and use it in GitHub Desktop.
Maximum common substring multi lang - codesignal test
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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