peach.crushed
BAN USERMaintain a map with <key, value> as <char, repetitions>.
While iterating over each word, populate a list of prefixes and another list of suffixes. Also, populate the repetitions map.
Again, iterate over both the lists and add the char and it's repetitions in the map, if the existing repetitions for that character does not exist in the map or if the repetitions are less than summation of suffix length+prefix length. While doing this make sure to avoid using the same word for calculating summation.
public class LongestSequence {
static Map<String, Integer> repeats = new HashMap<>();
static List<String> starts = new ArrayList<>();
static List<String> ends = new ArrayList<>();
static String maxRepChar = "";
public static void main(String[] args) {
String[] tests = {"ab", "ba", "aac", "dffffg"};
for (String test : tests) {
processor(test);
}
for (int i = 0; i < ends.size(); i++) {
String end = ends.get(i);
int endCharLength = end.length();
String character = end.substring(endCharLength - 1, endCharLength);
for (int j = 0; j < starts.size(); j++) {
if (j == i) continue;
else {
String start = starts.get(j);
int totalLength = endCharLength + start.length();
if ( start.startsWith(character) && (!repeats.containsKey(character) || repeats.get(character) < totalLength) ) {
repeats.put(character, totalLength);
if (totalLength > (repeats.get(maxRepChar) == null ? 0 : repeats.get(maxRepChar) )) {
maxRepChar = character;
}
}
}
}
}
System.out.println("maxRepChar = " + maxRepChar);
}
private static void processor(String test) {
Matcher repeatsMatcher = Pattern.compile("(.)\\1+").matcher(test);
while (repeatsMatcher.find()) {
String character = repeatsMatcher.group(1);
int repLength = repeatsMatcher.group(0).length();
if ( !repeats.containsKey(character) || repeats.get(character) < repLength) {
repeats.put(character, repLength);
if (repLength > (repeats.get(maxRepChar) == null ? 0 : repeats.get(maxRepChar) )) {
maxRepChar = character;
}
}
}
Matcher startsMatcher = Pattern.compile("^(.)\\1*").matcher(test);
if(startsMatcher.find()) {
starts.add(startsMatcher.group(0));
}
Matcher endsMatcher = Pattern.compile("(.)\\1*$").matcher(test);
if (endsMatcher.find()) {
ends.add(endsMatcher.group(0));
}
}
}
O(n)
- peach.crushed August 12, 2013