1044. Longest Duplicate Substring

not accepted

T: O(nlogn)

S: O(n)

class Solution {
    public String longestDupSubstring(String s) {
        int len = s.length();
        int left = 0;
        int right = len - 1;
        Map<Integer, Integer> map = new HashMap<>();
        while (left + 1 < right) {
            int mid = left + (right - left)/2;
            if (found(s, mid, map)) {
                left = mid;
            } else {
                right = mid;
            }
        }
        if (found(s, right, map)) { // right is longer, test first
            int start = map.get(right);
            System.out.println(start);
            return s.substring(start, start + right);
        }
        if (found(s, left, map)) {
            int start = map.get(left);
            return s.substring(start, start + left);
        }
        return "";
    }
    private boolean found(String s, int len, Map<Integer, Integer> map) {
        long hash = 0L;
        long base = 26L;
        long mod = 100_000_007L;
        Set<Long> set = new HashSet<>();
        long powBaseLen = 1L;
        for (int i = 0; i < len; i++) {
            powBaseLen = (powBaseLen*base) % mod;
        }
        
        for (int i = 0; i < s.length(); i++) {
            
            hash = (hash * base + (s.charAt(i) - 'a')) % mod;
            if (i >= len) {
                hash = (hash - (s.charAt(i-len) - 'a')*powBaseLen%mod + mod)%mod;
            }
            if (i >= len-1) { // sliding window has new value, 才要檢查 or 塞入 hash
                if (set.contains(hash)) {
                    map.put(len, i - len + 1);// 0 1 2 3
                    return true;
                }
                set.add(hash);
            }
        }
        return false;
        
    }
}