[leetcode #1044] Longest Duplicate Substring

Problem

Given a string s, consider all duplicated substrings: (contiguous) substrings of s that occur 2 or more times. The occurrences may overlap.

Return any duplicated substring that has the longest possible length. If s does not have a duplicated substring, the answer is "".

Example 1:

・ Input: s = "banana"
・ Output: "ana"

Example 2:

・ Input: s = "abcd"
・ Output: ""

Constraints:

・ 2 <= s.length <= 3 * 10⁴
・ s consists of lowercase English letters.

Idea

굉장히 어려운 문제다. 어떻게 풀려고 짱돌을 굴려봐도 답이 쉽사리 나오지 않는다. Bruth-force로 풀면 풀리긴 하겠지만 문자열의 길이가 최대 30,000이나 되기 때문에 O(n²)으로 풀면 Time Limit Exceeded가 뜨기 마련이다.

힌트를 보면 Rabin-Karp 알고리즘을 쓰라고 나온다. Rabin-Karp 알고리즘이 무엇인지 봤더니 string에 hash 값을 부여해 hash값을 비교하여 string이 동일한지 확인하는 알고리즘이었다. 동일한 Substring이 있는지 확인하는 문제기 때문에 길이가 같은 substring의 경우 char의 위치를 하나씩 옮겨가면서 hash값을 계산하면 전체 substring의 hash값을 매번 계산할 필요가 없어진다. 즉, hash값을 만드는 함수와 함께 다음 substring의 hash값을 효율적으로 계산할 수 있는 함수도 구현해야 한다.

그리고 비교할 substring의 길이를 정하는 것도 중요하다. Hash 값을 계산하는 연산이 O(n)이기 때문에, substring의 길이를 정하는 연산은 O(logn)이어야 한다. 이를 위해 binary search를 통해 substring의 길이를 정한다. 동일한 substring을 찾았을 경우, 비교할 substring의 길이를 증가시킨다. 찾지 못 했을 경우 substring의 길이를 감소시켜 동일한 substring이 있는지 확인한다. 이 때 증가 또는 감소시키는 길이는 1씩 더하거나 빼는 게 아니라 binary search를 기준으로 정한다.

복잡한 알고리즘을 사용하고 혼자 풀지도 못했지만, Rabin-Karp 알고리즘이 뭔지 알게 되었고, hash값을 이용해 string을 비교할 수 있다는 사실도 깨닫게 되었다. 한참동안 기억에 남을 문제가 될 듯!

Solution

class Solution {
    public String longestDupSubstring(String S) {
        String ans = "";

        int left = 1;
        int right = S.length()-1;

        while(left <= right){
            int m = left + (right - left)/2;
            String dup = getDup(m,S);

            if(dup != null){
                ans = dup;
                left = m+1;
            }else{
                right = m-1;
            }
        }

        return ans;
    }

    private String getDup(int size, String s){
        long H = hash(s.substring(0,size));

        HashSet<Long> set = new HashSet();
        set.add(H);

        long pow = 1;
        for(int i=1;i<size;i++)
            pow = (pow * 31);

        int n = s.length();
        for(int i=size;i < n;i++){
            H = nextHash(pow, H, s.charAt(i-size), s.charAt(i));
            if(!set.add(H)){
                return s.substring(i-size+1, i+1);
            }
        }

        return null;
    }

    private long hash(String s){
        long h = 0;
        long a = 1;

        int n = s.length();
        for(int k=n;k>=1;k--){
            char ch = s.charAt(k-1);
            h += (ch - 'a' + 1) * a;
            a = (a*31);
        }

        return h;
    }

    private long nextHash(long pow,long hash,char left,char right){
        return (hash - (left - 'a' + 1) * pow) * 31 + (right - 'a' + 1);
    }
}

Reference

https://leetcode.com/problems/longest-duplicate-substring