FastPrep
Problem · String

Find the longest possible regular expression

● HardAmazonINTERNOA
See Amazon hiring insights

All mistakes have been corrected. Thanks a lot for all the feedbacks from the Solutions! You guys are awesome! 🫡

Amazon developers are building a prototype for a regex generator for the given strings

For the prototype version, the regex consists of uppercase English letters, '[' and ']'.

For the prototype version, the regular expression is composed of uppercase English letters along with the characters '[' and ']'. In this case, any string of characters that is enclosed within the square brackets '[' and ']' will match any one of the characters in that string. It's important to note that the string inside the square brackets consists solely of uppercase English letters, and there is no repetition of characters within the brackets.

Here, a string of characters enclosed in square brackets '[' and ']' matches any of the one characters in that string.

Also, the string of characters enclosed within '[' and ']' consists of uppercase English letters only with no repetition.

For example:

  • "[ABBR]ABC" is not a valid regex as B occurs twice between square brackets.
  • "[]ABC", "A[A][", "][" and "]ABC" are also not valid regexes because brackets must contain some string and brackets should also form a balanced bracket sequence.
  • "[ABC]BC[A]" is a valid regex and matches with "BBCA" and "ABCA", but not with "ABBCA"
  • "[ABCZ][Q]" is a valid regex and matches with "AQ", "BQ", "CQ", "ZQ" but not with "DQ" or "ZC".
  • "[A][B][C][D]" is a valid regex and matches only with string "ABCD".

    • The errors in the above example were corrected on 06-19-2025, thanks to the helpful source shared by an awesome friend! Here is the relevant ss for your reference -

    Some very important notes for you to solve this question -- please read --

  • The length of a regular expression (regex) is defined as the total number of characters it contains. This count includes uppercase English alphabets along with special characters like '[' and ']', which are part of the syntax.
  • When comparing two strings, p and q, we determine which one is lexicographically smaller based on specific rules:

  • Moreover, the answer string, which needs to be returned, can grow significantly large, reaching up to an order of 10^6 for larger values of n. Hence, efficiency in computation and storage is a key consideration when dealing with such cases.

    • Function Description

    Let's complete the func in the editor on the right side of the screen ---->>>

    What parameters doesfindTheLongestPossibleRegularExpression get and what does it return?

    • x: a string :)
    • y: a string :O
    • z: a string :3

    Your task this time is to find the longest expression (a.k.a.regex) that is lexicographically smallest and matches both x and y but not z. If no such expression (regex) exists, return "-1".

    💐ᝰ.ᐟ animi༊·° and freya༊·° slay 🌷 👏

    Examples
    01 · Example 1
    x = "AB"
y = "BD"
z = "CD"
return = "[ABCDEFGHJKLMNOPQRSTUVWXYZ][ABCDEFGHJKLMNOPQRSTUVWXYZ]"
    Regex "[ABCDEFGHJKLMNOPQRSTUVWXYZ][ABCDEFGHJKLMNOPQRSTUVWXYZ]" matches with strings "AB" and "BD", but not with string "CD". Mistakes in this output were corrected.
    02 · Example 2
    x = "AERB"
y = "ATRC"
z = "AGCB"
return = "[ABCDEFGHIJKLMNOPQRSTUVWXYZ][ABCDEFGHIJKLMNOPQRSTUVWXYZ][ABDEFGHIJKLMNOPQRSTUVWXYZ][ABCDEFGHIJKLMNOPQRSTUVWXYZ]"
    Regex "[ABCDEFGHIJKLMNOPQRSTUVWXYZ][ABCDEFGHIJKLMNOPQRSTUVWXYZ][ABDEFGHIJKLMNOPQRSTUVWXYZ][ABCDEFGHIJKLMNOPQRSTUVWXYZ]" matches with strings "AERB" and "ATRC", but not with string "AGCB" 👉😳👈 Mistakes in this output were corrected.
    03 · Example 3
    x = "ABCD"
y = "CODE"
z = "CODE"
return = "-1"
    Here, x = "ABCD", y = "CODE", z = "CODE", As strings y and z are equal it is not possible that a regex matches with y but not z. In conclusion, the output is -1 🤧
    Constraints
  • 1 <= n <= 10^5
  • a, b and c consists of uppercase English letters only
    • More Amazon problems
    drafts saved locally
    public String findTheLongestPossibleRegularExpression(String x, String y, String z) {
  // write your code here
}
    x"AB"
    y"BD"
    z"CD"
    expected"[ABCDEFGHJKLMNOPQRSTUVWXYZ][ABCDEFGHJKLMNOPQRSTUVWXYZ]"
    checking account