Algorithm: Leetcode Contest 380

This time there are two interesting challenges, one is the follow-up of another.

Challenge 1

Find Beautiful Indices in the Given Array I

import java.util.*;

class Solution {
    public List<Integer> beautifulIndices(String s, String a, String b, int k) {
        char[] sc = s.toCharArray();
        char[] ac = a.toCharArray();
        char[] bc = b.toCharArray();
        // find all qualified j, and put them in treeset for the easy of query
        TreeSet<Integer> jIndexes = new TreeSet<>();
        for(int i = 0; i < sc.length; i++) {
            if (isQualified(sc, i, bc)) {
                jIndexes.add(i);
            }
        }
        
        // find all qualified i
        Set<Integer> iIndexes = new HashSet<>();
        for(int i = 0; i < sc.length; i++) {
            if (isQualified(sc, i, ac)) {
                iIndexes.add(i);
            }
        }
        
        List<Integer> res = new ArrayList<>();
        for(int i: iIndexes) {
            if (jIndexes.ceiling(i - k) != null && jIndexes.ceiling(i - k) <= i + k) {
                res.add(i);
            }
        }
        
        Collections.sort(res);
        
        return res;
    }
    
    private boolean isQualified(char[] s, int sIndex, char[] b) {
        if (sIndex + b.length > s.length) {
            return false;
        }
        
        for(int i = 0; i < b.length; i++) {
            if (b[i] != s[sIndex + i]) {
                return false;
            }
        }
        
        return true;
    }
}

Retro

When I solve the problem, there are several points need more attention

1. index calculation need to be done very carefully, I tune the index multiple times
2. usage of TreeSet, it can return null so need to do one more condition check
3. how to sort List, need to import “Collections” which under java.util package

Challenge 2

Find Beautiful Indices in the Given Array II

The finale is enhanced version of challenge 1, the problem description is same, while this challenge has more strict time limitation.

The part need to improve is how we find substring, currently time complexity is O(M * N) where M is length of s and N is length of substring.

If we adopt KMP algorithm, we can improve this algorithm to O(N).

I have another article introducing KMP, link

Implementation

public List<Integer> beautifulIndices(String s, String a, String b, int k) {
        
        char[] sc = s.toCharArray();
        char[] ac = a.toCharArray();
        char[] bc = b.toCharArray();
        // find all qualified j, and put them in treeset for the easy of query
        TreeSet<Integer> jIndexes = new TreeSet<>(findAllMatch(sc, bc));
        
        
        // find all qualified i
        Set<Integer> iIndexes = findAllMatch(sc, ac);
        
        List<Integer> res = new ArrayList<>();
        for(int i: iIndexes) {
            if (jIndexes.ceiling(i - k) != null && jIndexes.ceiling(i - k) <= i + k) {
                res.add(i);
            }
        }
        
        Collections.sort(res);
        
        return res;
    }
    
    private Set<Integer> findAllMatch(char[] str, char[] match) {
        int i = 0, j = 0;
        Set<Integer> res = new HashSet<>();
        
        int[] next = getNextArray(match);
        
        while (i < str.length) {
            while(i < str.length && j < match.length) {
                if (str[i] == match[j]) {
                    i++;
                    j++;
                } else if (j == 0) {
                    i++;
                } else {
                    j = next[j];
                }
            }

            if (j == match.length) {
                if (flag == 1) {
                    System.out.println(i - j);
                }
                
                res.add(i - j);
                j = next[j];
            }
        }
        
        return res;
        
    }
    
    private int[] getNextArray(char[] match) {
        if (match.length == 1) {
            return new int[]{0, 0};
        }
        
        int[] res = new int[match.length + 1];
        res[0] = -1;
        res[1] = 0;
        int i = 2, position = 0;
        
        while(i < res.length) {
            if (match[i - 1] == match[position]) {
                res[i++] = ++position; 
            } else if (position == 0) {
                i++;
            } else {
                position = res[position];
            }
        }
        

        return res;
    }
}

Retro

• Understanding KMP itself is tricky
• when find qualified match string, how to determine next position to resume the process
• final position of next array should be counted as well