1044. Longest Duplicate Substring

gistfile1.txt

// (X) 63 / 67 test cases passed.
class Solution {
    long BASE = 26;
    long MOD = 1 << 31 - 1;
    public String longestDupSubstring(String s) {
        //rolling hash + binary search
        //ex: banana, is any length contains duplicate string?
        //(Y)length1: b, a, n
        //(Y)length2: ba, an, na
        //(Y)length3: ban,ana,nan
        //(N)length4: bana, anan, nana
        //(N)length5: banan, anana
        //(N)length6: banana
        //-> can use binary search to find max length contains duplicate string
        
        int left = 1;
        int right = s.length();
        String result = "";
        while(left < right) {
            int mid = left + (right - left) / 2;
            String temp = duplicateSubstring(s, mid);
            if(temp != null) {
                left = mid + 1;
                result = temp;
            } else {
                right = mid;
            }
        }
        return result;
    }
    
    private String duplicateSubstring(String s, int l) {
        Set<Long> set = new HashSet<>();
        
        long hash = 0;
        long deleteBase = 1;
        
        for(int i = 1; i < l; i++) {
            deleteBase = (deleteBase * BASE) % MOD;
        }
        
        for(int i = 0; i < s.length(); i++) {
            int current = s.charAt(i) - 'a';
            hash = ((hash * BASE) % MOD + current) % MOD;
            if(i + 1 >= l) {
                if(set.contains(hash)) {
                    return s.substring(i - l + 1, i + 1);
                }
                set.add(hash);
                hash = hash - ((deleteBase * (s.charAt(i - l + 1) - 'a'))% MOD);
            }
        }
        
        return null;
    }
}