Longest Substring Among Strings

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)$