Saturday, September 19, 2020

Longest string made up of only vowels ----M ~~~~~~~

Amazon OA:

You are given with a string . Your task is to remove atmost two substrings of any length from the given string such that the remaining string contains vowels('a','e','i','o','u') only. Your aim is the maximise the length of the remaining string. Output the length of remaining string after removal of atmost two substrings.
NOTE: The answer may be 0, i.e. removing the entire string.

Sample Input        --->  Sample Output

earthproblem    --->3
letsgosomewhere    ---> 2 



A:

Java clear and concise O(N) and O(1) solution with Playground to test.
Note:
Since we can only remove two substrings in the original string, this problem can be translated into this equivalent one: find the longest substring in S that all the chars in this substring are vowels. Be careful, we do not consider the all-vowels-substring which begin from the start and from the end when finding the longest, we just count them and add it to the final result.

a a a y y y a a y y a y a a a y a y a a a
^ ^ ^ - - - * * - - * - * * * - * - ^ ^ ^

The longest continuous all-vowels-substring is "aaa" start at index 12, so we keep this substrings and the first 3 chars and the last 3 chars to get the answer 9. Its valid since we only remove two substrings in this case.

private boolean isVowel(char c){
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
public int longestString(String s){
    int len = s.length();
    int start = 0, end = len - 1;
    while(start < len && isVowel(s.charAt(start))) ++start;
    while(end >= 0 && isVowel(s.charAt(end))) --end;
    // checking area come to [start, end]
    if(start >= len) return len;
    int res = start + len - 1 - end;
    int longest = 0, sum = 0;
    for(int i = start + 1; i <= end; ++i){
        if(isVowel(s.charAt(i)))
            ++sum;
        else
            sum = 0;
        longest = Math.max(sum, longest);
    }
    return longest + res;
}




No comments:

Post a Comment