- Published on
Longest Substring Among Strings
- Authors
- Name
- Humam Fauzi
Let's say we have three strings texas
, aslam
, donbas
. What is the longest substring that those three string share. All of them has substring as
.
How do we find longest substring from all of strings?
Base Function
Our input should be []string
and our output should be string
. So we can write the function as
func substring(list []string) string {
return ""
}
So what should we do? First we find the smallest string in our array. If we find two or more string have same length, we can choose whatever we like. To avoid cluttering the main function, let's create a new function.
Smallest String
func findSmallestString(list []string) string {
smallest := list[0]
for index, value := range list[1:] {
if len(value) < smallest {
smallest = list[index]
}
}
return smallest
}
We took the first string and and loop the rest of string. If the string in the loop is smaller than the first string, then it would take it place. The process keep going until the loop is done. This will guarantee that we find smalles string in the list.
Sliding Window
func substring(list []string) string {
smallest := findSmallestString(list)
for i:=len(smallest);i==0;i--{
windows := slidingWindow(smallest, i)
}
return ""
}
We add the first loop. The loop, instead of using usual increment loop, it uses decrement loop which start from smallest string length. Then we create a sliding window from it so we have all possible substring for n-number of string where n is equal to i
. The explanation about sliding window can be found here. We used the generalized form so we also need to input type. We convert it to []rune
so it can be iterated and sliced.
func substring(list []string) string {
smallest := findSmallestString(list)
for i:=len(smallest);i==0;i--{
windows := slidingWindow[rune]([]rune(smallest), i)
for _, win := range windows {
if isExistInAllList(list, string(win)) {
return string(win)
}
}
}
return ""
}
We add the second loop where we iterate all possible substring and check it with our original list using isExistInAllList
which we will later create. If the function said the substring exist in every list member, then we found the answer because we using decrement loop that evaluate the substring from long to short. We convert the win
which has type of []rune
, back to string. (We can also use byte here but for some reason I think of rune data type)
Is Exist In All List
func isExistInAllList(list, win) {
final := true
for _, word := range list {
if !strings.Contain(word, win) {
return false
}
}
return final
}
The function have intial value of true
. We loop all possible string (including the smallest one which we can remove for slight better performance) and check whether it is contained the substring win
using native library strings.Contain
. If one of the string does not contain the substring, then we immediately return false
since we need all list to contain the substring in order to return true
value. So let's our final and complete function.
Complete Function
func slidingWindow[T comparable](input []T, member int) [][]T {
if member > len(input) {
member = len(input)
}
fmt.Println(input)
totalMember := len(input) - (member - 1)
final := make([][]T, totalMember)
for i := 0; i < totalMember; i++ {
final[i] = input[i : i+member]
}
return final
}
func findSmallestString(list []string) string {
smallest := list[0]
for index, value := range list[1:] {
if len(value) < len(smallest) {
smallest = list[index]
}
}
return smallest
}
func isExistInAllList(list []string, win string) bool {
final := true
for _, word := range list {
if !strings.Contains(word, win) {
return false
}
}
return final
}
func substring(list []string) string {
smallest := findSmallestString(list)
for i := len(smallest); i != 0; i-- {
windows := slidingWindow[rune]([]rune(smallest), i)
for _, win := range windows {
if isExistInAllList(list, string(win)) {
return string(win)
}
}
}
return ""
}
We have three subfunction and one main function substring
. We can merge it to one function but there will be a lot of indentation which reduce code comperhension. We have a five loops here. When we want to know the worst case runtime, we need to look the longest for loop and nested for loop. In this case we have three nested deep for loops.
- First, is the decrement of smallest string.
- Second, is the window substring loop (which actually have two loop but on the same level).
- Third is the looping the list.
To get the worst case scenario, we need to multiply all worst case scenario in the nested loop. So our first variable is the length of the smallest variable . The second variable is sliding window which its runtime decided by increment. In the worst case it would be the smallest increment which equal to sv
. The third variable defined by how many strings we need to check . So our notation would be