50 DSA-Questions: #15, #16

#15. Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

public class Exercise15 {
    private final String INPUT = "abcabcbb"; // abc
    // private final String INPUT = "abcadbcbb"; // bcad
    //private final String INPUT = "pwwkew"; // wke
    // private final String INPUT = "georgiana"; // eorgian
    // private final String INPUT = "georoi"; // geor
    // private final String INPUT = "gerryinyr"; // ryin

    private boolean containsChar(String content, char currentChar) {
        return content.chars().filter(ch -> ch == currentChar).findFirst().isPresent();
    }

    private String replaceCharAtTheEnd(String content, char stripped) {
        int index = content.indexOf(stripped);
        return content.concat(String.valueOf(stripped)).substring(index + 1);
    }

    private void solve() {
        assert(!INPUT.isEmpty());

        String currentStrike = String.valueOf(INPUT.charAt(0));
        String bestStrike = currentStrike;

        for (int i=1; i<INPUT.length(); i++) {
            final char currentChar = INPUT.charAt(i);
            if (!containsChar(currentStrike, currentChar)) {
                currentStrike = currentStrike.concat(String.valueOf(currentChar)); // continue current strike
            } else {
                if (currentStrike.length() > bestStrike.length()) {
                    bestStrike = currentStrike;
                }
                currentStrike = replaceCharAtTheEnd(currentStrike, currentChar); // reset strike
            }
        }

        System.out.println(currentStrike.length() > bestStrike.length() ? currentStrike : bestStrike);
    }


    public static void main(String args[]) {
        new Exercise15().solve();
    }
}

#16. Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations.

public class Exercise16 {
    // private final String INPUT = "ABAB"; // B->A , B->A => AaAa, size of the longest repeating consecutive char = 4
    // private final String INPUT = "ADFAAED"; // AaaAAEG, size = 5
    // private final String INPUT = "PGAPTARGKLGZ"; // PppPTARGKLGZ, size = 4
    // private final String INPUT = "GEO"; // Ggg, size = 3
    // private final String INPUT = "ABCDEFGHA"; // AaaDEFGHA, size = 3
    // private final int K = 2;

    private final String INPUT = "ANAAREMERELE"; // ANAAREeEeEeE, size = 7
    private final int K = 3;

    private Map<Character, Occurrence> occurrenceMap() {
        Map<Character, Occurrence> map = new HashMap<>();
        for (int i=0; i<INPUT.length(); i++) {
            char key = INPUT.charAt(i);
            if (map.containsKey(key)) {
                Occurrence occurrence = map.get(key);
                occurrence.addIndex(i);
            } else {
                map.put(key, new Occurrence(i));
            }
        }
        return map;
    }

    private List<Map.Entry<Character, Occurrence>> filterSortDesc(Map<Character, Occurrence> map) {
        return map.entrySet().stream()
                .filter(entry -> entry.getValue().getCount() > 1)
                .sorted((e1, e2) -> e2.getValue().findMaxConsec() - e1.getValue().findMaxConsec())
                .collect(Collectors.toList());
    }
    
    private int getDefaultProfit() {
        return (K < INPUT.length() ? K+1 : INPUT.length());
    }

    private void solve() {
        assert(!INPUT.isEmpty());

        List<Map.Entry<Character, Occurrence>> sortedEntries = filterSortDesc(occurrenceMap());
        if (sortedEntries.isEmpty()) {
            System.out.println("Max = " + getDefaultProfit());
            return;
        }

        System.out.println("Max = " + sortedEntries.get(0).getValue().getMaxConsec());
    }

    public static void main(String args[]) {
        new Exercise16().solve();
    }

    private class Occurrence {
        private List<Integer> indexes;
        private int maxConsec;

        public Occurrence(int index) {
            this.indexes = new ArrayList<>();
            this.addIndex(index);
        }

        public void addIndex(Integer index) {
            this.indexes.add(index);
        }

        public int getCount() {
            return indexes.size();
        }

        public int findMaxConsec() {
            int credit = K;
            int maxProfit = 0;
            for (int i=0; i<indexes.size()-1; i++, credit = K) {
                int profit = 0;
                if (credit >= indexes.get(i+1) - indexes.get(i) - 1) { // can afford a strike
                    credit -= indexes.get(i+1) - indexes.get(i) - 1; // extract from K
                    profit = indexes.get(i+1) - indexes.get(i) - 1 + 2; // no. elements comprised

                    // INPUT[indexes.get(i)] == INPUT[indexes.get(i+1)]

                    for (int j=indexes.get(i+1) + 1; j<INPUT.length(); j++) { // go right
                        if (INPUT.charAt(j) == INPUT.charAt(indexes.get(i))) { // free one
                            profit++;
                        }
                        else {
                            if (credit > 0) { // buy one
                                profit++;
                                credit--;
                            } else {
                                break;
                            }
                        }
                    }

                    for (int j=indexes.get(i) - 1; j>=0; j--) { // go left
                        if (INPUT.charAt(j) == INPUT.charAt(indexes.get(i))) { // free one
                            profit++;
                        } else {
                            if (credit > 0) { // buy one
                                profit++;
                                credit--;
                            } else {
                                break;
                            }
                        }
                    }
                }

                if (profit > maxProfit) {
                    maxProfit = profit;
                }
            }

            if (maxProfit == 0) {
                maxProfit = getDefaultProfit();
            }

            this.maxConsec = maxProfit;
            return maxProfit;
        }

        public int getMaxConsec() {
            return maxConsec;
        }
    }
}