Overview

A string and a dictionary of words are given. The objective is to find the longest word in the dictionary which is present as a subsequence in the given string. If the number of possible results is more than 1 then return the longest word with the smallest lexicographical order.

Example 1

s = "mbacnago", dictionary = ["ale","mango","monkey","plea"]
Output: "mango"

Example 2

s = "mbacnago", dictionary = ["ba","ag"]
Output: "ag"

Program

Below is the program for the same

package main

import (
	"fmt"
	"sort"
)

func findLongestWord(s string, dictionary []string) string {
	sort.Slice(dictionary, func(i, j int) bool {
		lenI := len(dictionary[i])
		lenJ := len(dictionary[j])

		if lenI == lenJ {
			return dictionary[i] < dictionary[j]
		}

		return lenI > lenJ
	})

	lenS := len(s)

	for i := 0; i < len(dictionary); i++ {
		if isSubstring(s, dictionary[i], lenS) {
			return dictionary[i]
		}
	}

	return ""
}

func isSubstring(s string, sub string, lenS int) bool {
	lenSub := len(sub)

	if lenSub == 0 {
		return true
	}

	if lenSub > lenS {
		return false
	}

	for i, j := 0, 0; i < lenS && j < lenSub; {
		if i+lenSub-j-1 >= lenS {
			return false
		}
		if s[i] == sub[j] {
			j++
		}
		if j == lenSub {
			return true
		}
		i++
	}

	return false
}

func main() {
	output := findLongestWord("mbacnago", []string{"ale", "mango", "monkey", "plea"})
	fmt.Println(output)

	output = findLongestWord("mbacnago", []string{"ba", "ag"})
	fmt.Println(output)

}

Output

mango
ag

Also, check out our system design tutorial series here – System Design Tutorial Series