O(input string length) runtime
import java.util.*;
public class Main {
/*
algo:
keep map of runningLongestSubsequence that ends in each letter. loop through String s. for each char, try appending
to runningLongestSubsequence for that char, as well as to runningLongestSubsequence for preceding char.
update map with whichever results in longer subsequence.
for String s = "ieaeiouiaooeeeaaeiou", final map is:
terminal letter in longest running subsequence-> longest running subsequence
a -> aaaa
e -> aeeeee
i -> aeeeeei
o -> aeeeeeio
u -> aeeeeeiou
naming:
precCharMap - precedingCharMap
runningLongestSubMap - runningLongestSubsequenceMap
*/
public static int longestSubsequence(String s) {
if (s.length() <= 0) throw new IllegalArgumentException();
Map<Character, Character> precCharMap = new HashMap<>();
precCharMap.put('u', 'o');
precCharMap.put('o', 'i');
precCharMap.put('i', 'e');
precCharMap.put('e', 'a');
Map<Character, String> runningLongestSubMap = new HashMap<>();
for (char currChar : s.toCharArray()) {
//get longest subs
String currCharLongestSub;
String precCharLongestSub = null;
if (currChar == 'a') {
currCharLongestSub = runningLongestSubMap.getOrDefault(currChar, "");
} else {
currCharLongestSub = runningLongestSubMap.get(currChar);
char precChar = precCharMap.get(currChar);
precCharLongestSub = runningLongestSubMap.get(precChar);
}
//update running longest subsequence map
if (precCharLongestSub == null && currCharLongestSub != null) {
updateRunningLongestSubMap(currCharLongestSub, currChar, runningLongestSubMap);
} else if (currCharLongestSub == null && precCharLongestSub != null) {
updateRunningLongestSubMap(precCharLongestSub, currChar, runningLongestSubMap);
} else if (currCharLongestSub != null && precCharLongestSub != null) {
//pick longer
if (currCharLongestSub.length() < precCharLongestSub.length()) {
updateRunningLongestSubMap(precCharLongestSub, currChar, runningLongestSubMap);
} else {
updateRunningLongestSubMap(currCharLongestSub, currChar, runningLongestSubMap);
}
}
}
if (runningLongestSubMap.get('u') == null) {
return 0;
}
return runningLongestSubMap.get('u').length();
}
private static void updateRunningLongestSubMap(String longestSub, char currChar,
Map<Character, String> runningLongestSubMap) {
String currCharLongestSub = longestSub + currChar;
runningLongestSubMap.put(currChar, currCharLongestSub);
}
public static void main(String[] args) {
//String s = "aeeiooua"; //7
//String s = "aeiaaioooaauuaeiou"; //10
String s = "ieaeiouiaooeeeaaeiou"; //9
//String s = "ieaeou"; //0
//String s = "ieaeoooo"; //0
//String s = "aeiou"; //5
//if u have String s beginning in "ao", it'll do nothing with o and
//continue on to index 2.
System.out.println(longestSubsequence(s));
}
}