Amazon OA | SDE Intern | Longest Substring

Question

Answer 1

public static int findMaxRegexMatch(String sourceString, String pattern) {

        String[] parts = pattern.split("\\*", -1);

        String prefix = parts[0];

        String suffix = parts[1];

        int firstPrefixIndex = sourceString.indexOf(prefix);

        int lastSuffixIndex = sourceString.lastIndexOf(suffix);

        if (firstPrefixIndex != -1 && lastSuffixIndex != -1 &&

            (firstPrefixIndex + prefix.length() <= lastSuffixIndex)) {

            return (lastSuffixIndex + suffix.length()) - firstPrefixIndex;

        }

        return -1;

    }

}

Answer 2

def findMaxRegexMatch(sourceString, regex):

    first_part_regex = regex.split("*")[0]

    second_part_regex = regex.split("*")[1]

    longest_match_length = 0

 

    if first_part_regex in sourceString:

        longest_match_length = len(first_part_regex)

        second_half_string = sourceString.split(first_part_regex)[-1]

 

        if second_part_regex in second_half_string:

            for i in range(len(second_half_string.split(second_part_regex)) - 1):

                longest_match_length += len(second_half_string.split(second_part_regex)[i])

            longest_match_length += (len(second_half_string.split(second_part_regex)) - 1) * len(second_part_regex)

            return longest_match_length

        else:

            return -1

    else:

        return -1

 

print(findMaxRegexMatch("abcde", "a*b"))

print(findMaxRegexMatch("abcde", "a*c"))

print(findMaxRegexMatch("abcde", "a*d"))

print(findMaxRegexMatch("abcde", "a*e"))

print(findMaxRegexMatch("abcdeb", "a*b"))

print(findMaxRegexMatch("abcde", "f*g"))