- 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 $sv$. 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 $w$. So our notation would be $O(sv^2 \cdot w)$