Pangram Checking - Find smallest substring that contains list of chars

Given a list of chars and a string, find the smallest sub string (start index and end index) that contains all the chars
For example:
Given { 'a', 'b', 'c' } and "aMmaddbFcFd" – Output should be: Start index: 3, End Index: 8 (note that ‘a’ also appears in index 0)
Given all alphabet chars and the pangram “The quick brown fox jumps over the lazy dog“ – Start index: 4, End Index: 42

Approach

  • Store the list of chars in a HashMap, where the key is the char, value is the last location of the char in the string (default –1).
  • Iterate over the stings, for each item lookup the char in the HashMap, if found, update the location with current index
  • Iterate over the HashMap, get the min location (or index) and max location, if any of the location is –1, it means that the char wasn’t found in the string..

Tests

public class StringListFinderTest {
    @Test
    public void testFind_duplicateStrings() throws CharNotFoundException {
        char[] arr = new char[] { 'a', 'b', 'c' };
        String input = "aMMaDDbFcFD";
        final StringListFinderResult result = StringListFinder.find(input, arr);

        assertEquals(result.minIndex, 3);
        assertEquals(result.maxIndex, 8);
    }

    @Test
    public void testFind_pangram() throws CharNotFoundException {
        char[] arr = "abcdefghijklmnopqrstuvwxyz".toCharArray();
        String input = "The quick brown fox jumps over the lazy dog";
        final StringListFinderResult result = StringListFinder.find(input, arr);

        assertEquals(result.minIndex, 4);
        assertEquals(result.maxIndex, 42);
    }

    @Test
    public void testFind_emptyChars() throws CharNotFoundException {
        char[] arr = new char[] {  };
        String input = "";
        final StringListFinderResult result = StringListFinder.find(input, arr);
        assertEquals(result.minIndex, 0);
        assertEquals(result.maxIndex, 0);
    }

    @Test(expected = CharNotFoundException.class)
    public void testFind_emptyString() throws CharNotFoundException {

        char[] arr = new char[] { 'a', 'b', 's' };
        String input = "";
        StringListFinder.find(input, arr);
    }

    @Test(expected = CharNotFoundException.class)
    public void testFind_missingChar() throws CharNotFoundException {
        char[] arr = new char[] { 'a', 'b', 's' };
        String input = "aMMaDDbFcFD";
        StringListFinder.find(input, arr);
    }
}

Solution

public class StringListFinder {

    public static StringListFinderResult find(String input, char[] arr) throws CharNotFoundException {
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            char c = arr[i];
            map.put(c, -1);
        }

        // Update the latest index
        for (int index = 0; index < input.length(); index++) {
            char c = input.charAt(index);
            if (map.containsKey(c)) {
                map.put(c, index);
            }
        }
        int min = arr.length, max = 0;

        final Collection<Integer> values = map.values();
        for (int value: values) {
            if (value == -1) {
                throw new CharNotFoundException("Couldn't find all chars");
            }
            if (value < min) {
                min = value;
            } if (value > max) {
                max = value;
            }
        }
        
        return new StringListFinderResult(min, max);
    }
}
public class StringListFinderResult {
    int minIndex, maxIndex = 0;

    public StringListFinderResult(int minIndex, int maxIndex) {
        this.minIndex = minIndex;
        this.maxIndex = maxIndex;
    }

    @Override
    public String toString() {
        return "Result{" +
                "minIndex=" + minIndex +
                ", maxIndex=" + maxIndex +
                '}';
    }
}

Comments

  1. This solution is actually wrong. It wont work for a string like this: abcrgmfa
    In this case, the last 'a' will contain its index in the hash map, even though it should be the first one.

    ReplyDelete

Post a Comment