DistinctCharSubstrings.java

package co.in.shoonya.abc.prep.ds.classic.strings;

// Given a string of characters (a, b, c,....z), we want to break the string into a maximum number of substrings
// in which every character comes in only one substring. We have to return length of all substrings.
// Ex 1: Input string = "abcdefgahijklhopqrsot"
// Output = [8, 5, 6, 1]
// Ex 2: Input string = "abcd"
// Output = [1, 1, 1, 1]

import java.util.*;

public class DistinctCharSubstrings {
    public static void main(String[] args) {
        //abcdefgahijklhopqrsot
        //abcdaefbghii
        System.out.println(Arrays.toString(lengthDistinctCharSubstrings("abcdaefbghii")));
    }

    private static int[] lengthDistinctCharSubstrings(String str) {
        List<String> substrings = new ArrayList<String>();
        List<CharWithEndIndex> data = new ArrayList<>();
        Map<Character, Integer> beginPositions = new HashMap<>();
        int charIndex = 0;
        for (char c : str.toCharArray()) {
            if (!beginPositions.containsKey(c)) {
                beginPositions.put(c, charIndex);
                data.add(new CharWithEndIndex(c, charIndex));
            } else {
                data.add(new CharWithEndIndex('$', charIndex));
                data.set(beginPositions.get(c), new CharWithEndIndex(c, charIndex));
            }
            charIndex++;
        }
        int endIdx = -1;
        int maxIdx = -1;
        for (int subIdx = 0; subIdx < data.size(); ) {
            endIdx = data.get(subIdx).endIdx;
            maxIdx = endIdx;
            for (int idx = subIdx; idx < endIdx; idx++) {
                maxIdx = Math.max(maxIdx, data.get(idx).endIdx);
            }
            substrings.add(subIdx == maxIdx ? str.substring(subIdx, subIdx + 1) : str.substring(subIdx, maxIdx + 1));
            subIdx = subIdx == maxIdx ? subIdx + 1 : maxIdx + 1;
            if (subIdx == maxIdx)
                break;
        }

        return substrings.stream().mapToInt(i -> i.length()).toArray();
    }

    private static class CharWithEndIndex {
        private char c;
        private int endIdx;

        public CharWithEndIndex(char c, int endIdx) {
            this.c = c;
            this.endIdx = endIdx;
        }

        @Override
        public String toString() {
            return "Pair{" +
                    "c=" + c +
                    ", endIdx=" + endIdx +
                    "}n";
        }
    }
}