Probleme Strings

#1. First non-repeating character

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

class Solution {

    public int firstUniqChar(String str) {

        Map<Character,Integer> map = new HashMap<>();

        for (int i=0; i<str.length(); i++) {

            Integer count = map.get(str.charAt(i));

            map.put(str.charAt(i), count == null ? 1 : count + 1);

        }

        for (int i=0; i<str.length(); i++) {

            if (map.get(str.charAt(i)) == 1) {

                return i;

            }

        }

        return -1;

    }

    public int firstUniqChar_2(String str) { // str contains only lowercase letters 'a' t o 'z'

        int bitVector = 0;

        int unique = (int) Math.pow(2, 27) - 1; // 1....1 for 26 bits corresponding to 'a' to 'z'

        for (int i=0; i<str.length(); i++) {

            int index = str.charAt(i) - 'a';

            if ((bitVector & (1 << index)) > 0) { // if bit index already set

                unique = unique & ~(1 << index); // clear bit at index

            }

            bitVector = bitVector | (1 << index); // set bit at index

        }

        for (int i=0; i<str.length(); i++) {

            int index = str.charAt(i) - 'a';

            boolean isBitSet = (unique & (1 << index)) > 0;

            if (isBitSet) {

                return i;

            }

        }

        return -1;

    }

}

#2. Permutation of a palindrome

Given a string, return if it is a permutation of a palindrome. 

class Solution {

    public boolean canBecomePalindrome(String str) {

        if (str.length() == 0) {

            return false;

        }

 

        int bitVector = 0;

        for (int i=0; i<str.length(); i++) {

            int index = str.charAt(i) - 'a';

            if ((bitVector & (1 << index)) > 0) { // if bit set

                bitVector = bitVector & ~(1 << index); // clear

            } else {

                bitVector = bitVector | (1 << index); // set

            }

        }

 

        // se poate transforma in palindrom daca:

        // Are nr par de caractere si toti bitii 0, SAU

        // nr impar de caractere si un singur bit 1

 

        boolean evenAmountOfChar = str.length() % 2 == 0;

        boolean hasBit1 = false;

        for (int i=0; i<26; i++) { // 26 letters in alphabet

            if ((bitVector & (1 << i)) > 0) { // if bit set

                if (hasBit1) {

                    return false; // a second bit is set

                }

                hasBit1 = true;

            }

        }

 

        return evenAmountOfChar ^ hasBit1;

    }

}

50 DSA-Questions: String #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;
        }
    }
}