Avoiding Regular Expression (Regex) Worst Case
The "obvious" regular-expression-based solution for this problem (a+e+i+o+u+) will have quadratic performance on a string of all "a"s.\n\nThis is due to the beh
The "obvious" regular-expression-based solution for this problem (`a+e+i+o+u+`) will have quadratic performance on a string of all "a"s.\n\nThis is due to the behavior of regular expression matchers. It will start at the first character, attempt to make a match, and scan to the end of the string to discover that no match exists. It will then start at the second character and try again, then the third, etc.\n\nThis behavior can be circumvented by exploiting the fact that most regular expression matchers do not allow overlapping matches. That means if the regex is "loosened" so that strings of "a"s are always considered a match, the matcher won\'t try each character individually.\n\nThe regex to use is `(a+)(e+i+o+u+)?`. You then simply have to filter away all matches that don\'t have the optional second group.(Alternatively, if you\'re clever you can use non-capturing groups and check that the last character is a `u`).\n\nHere is an example in Python:\n\n```\nimport re\n\ndef longestBeautifulSubstring(self, word: str) -> int:\n    if len(word) < 5:\n        return 0\n\n    lengths = [len(a) + len(opt) for (a, opt) in re.findall(r\'(a+)(e+i+o+u+)?\', word) if opt]\n    return max(lengths) if lengths else 0\n```
[]