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

Answer 3

1. Split the regex string into two parts at the '*':

   - prefix = part before '*'

   - suffix = part after '*'

2. Loop through every starting index i in the text:

   - Check if the prefix matches the text starting at i.

   - If yes, loop through all positions j starting from i + prefix length to text end:

       - Check if the suffix matches the text at position j.

       - If yes, calculate substring length = (end of suffix - start of prefix)

       - Keep track of maximum length found.

3. After checking all possibilities, return the maximum length.

   - If no match found, return -1.

#include <iostream>

using namespace std;

// Function to check if a pattern matches text starting at index i

bool matchesAt(const string &text, const string &pattern, int i) {

    if (i + pattern.length() > text.length()) return false;

    for (int j = 0; j < pattern.length(); j++) {

        if (text[i + j] != pattern[j]) return false;

    }

    return true;

}

int getLongestMatch(string text, string regex) {

    // Step 1: Split regex into prefix and suffix

    int star = -1;

    for (int i = 0; i < regex.length(); i++) {

        if (regex[i] == '*') {

            star = i;

            break;

        }

    }

    string prefix = "";

    string suffix = "";

    for (int i = 0; i < star; i++) prefix += regex[i];

    for (int i = star + 1; i < regex.length(); i++) suffix += regex[i];

    int maxLen = -1;

    // Step 2: Loop through all starting positions

    for (int i = 0; i < text.length(); i++) {

        // Check if prefix matches at i

        if (matchesAt(text, prefix, i)) {

            // Step 3: Check all possible suffix positions after prefix

            for (int j = i + prefix.length(); j <= text.length() - suffix.length(); j++) {

                if (matchesAt(text, suffix, j)) {

                    int len = j + suffix.length() - i;

                    if (len > maxLen) maxLen = len;

                }

            }

        }

    }

    return maxLen;

}

int main() {

    cout << getLongestMatch("hackerrank", "ack*r") << endl;    // 6

    cout << getLongestMatch("programming", "r*in") << endl;    // 9

    cout << getLongestMatch("debug", "ug*eb") << endl;         // -1

    return 0;

}