1044. Longest Duplicate Substring

LeetCode hard original: C# #csharp #hard #hash-table #leetcode #search #string #tree #two-pointers

O texto da tarefa é traduzido do russo para o idioma selecionado. O código permanece sem alterações.

LeetCode Static

given строку s, рассмотрите все дублированные подстроки: (смежные) подстроки s, которые встречаются 2 или более раз.Вхождения могут перекрываться. return любую дублированную подстроку, которая имеет наибольшую возможную длину.Если в s нет дублирующейся подстроки, ответом будет "".

Exemplo:

Input: s = "banana"

Output: "ana"

C# solução

correspondente/original

public class Solution {
    public string LongestDupSubstring(string s) {
        int left = 1, right = s.Length;
        string result = "";
        while (left < right) {
            int mid = (left + right) / 2;
            string dup = Search(s, mid);
            if (dup != null) {
                result = dup;
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return result;
    }
    private string Search(string s, int length) {
        HashSet<string> seen = new HashSet<string>();
        for (int i = 0; i <= s.Length - length; i++) {
            string sub = s.Substring(i, length);
            if (seen.Contains(sub)) {
                return sub;
            }
            seen.Add(sub);
        }
        return null;
    }
}

C++ solução

rascunho automático, revisar antes de enviar

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string LongestDupSubstring(string s) {
        int left = 1, right = s.size();
        string result = "";
        while (left < right) {
            int mid = (left + right) / 2;
            string dup = Search(s, mid);
            if (dup != null) {
                result = dup;
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return result;
    }
    private string Search(string s, int length) {
        HashSet<string> seen = new HashSet<string>();
        for (int i = 0; i <= s.size() - length; i++) {
            string sub = s.Substring(i, length);
            if (seen.Contains(sub)) {
                return sub;
            }
            seen.push_back(sub);
        }
        return null;
    }
}

Java solução

correspondente/original

public class Solution {
    public String longestDupSubstring(String s) {
        int n = s.length();
        int[] nums = new int[n];
        for (int i = 0; i < n; ++i) nums[i] = (int)s.charAt(i) - (int)'a';
        int a = 26;
        long modulus = (long)Math.pow(2, 32);
        
        int left = 1, right = n;
        String result = "";
        while (left < right) {
            int mid = (left + right) / 2;
            String dup = search(mid, a, modulus, n, nums);
            if (dup != null) {
                result = dup;
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return result;
    }

    private String search(int L, int a, long modulus, int n, int[] nums) {
        long h = 0;
        for (int i = 0; i < L; ++i) h = (h * a + nums[i]) % modulus;
        HashSet<Long> seen = new HashSet<>();
        seen.add(h);
        long aL = 1;
        for (int i = 1; i <= L; ++i) aL = (aL * a) % modulus;
        for (int start = 1; start < n - L + 1; ++start) {
            h = (h * a - nums[start - 1] * aL % modulus + modulus) % modulus;
            h = (h + nums[start + L - 1]) % modulus;
            if (seen.contains(h)) return s.substring(start, start + L);
            seen.add(h);
        }
        return null;
    }
}

JavaScript solução

correspondente/original

function longestDupSubstring(s) {
    function search(len) {
        let seen = new Set();
        for (let i = 0; i <= s.length - len; i++) {
            let sub = s.slice(i, i + len);
            if (seen.has(sub)) {
                return sub;
            }
            seen.add(sub);
        }
        return "";
    }

    let left = 1, right = s.length;
    let result = "";
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        let dup = search(mid);
        if (dup) {
            result = dup;
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return result;
}

Python solução

correspondente/original

def longestDupSubstring(s):
    n = len(s)
    mod = 2**63 - 1

    def search(length):
        p = 26
        current_hash = 0
        p_length = pow(p, length, mod)
        hashes = set()

        for i in range(length):
            current_hash = (current_hash * p + ord(s[i])) % mod
        
        hashes.add(current_hash)
        
        for i in range(length, n):
            current_hash = (current_hash * p + ord(s[i]) - ord(s[i - length]) * p_length) % mod
            if current_hash in hashes:
                return i - length + 1
            hashes.add(current_hash)
        
        return -1

    left, right = 1, n - 1
    result = ""
    
    while left <= right:
        mid = (left + right) // 2
        start = search(mid)
        if start != -1:
            result = s[start:start + mid]
            left = mid + 1
        else:
            right = mid - 1
    
    return result

Go solução

correspondente/original

package main

import (
    "fmt"
    "strings"
)

func longestDupSubstring(s string) string {
    search := func(length int) string {
        seen := make(map[string]bool)
        for i := 0; i <= len(s)-length; i++ {
            sub := s[i : i+length]
            if seen[sub] {
                return sub
            }
            seen[sub] = true
        }
        return ""
    }

    left, right := 1, len(s)
    result := ""
    for left < right {
        mid := (left + right) / 2
        dup := search(mid)
        if dup != "" {
            result = dup
            left = mid + 1
        } else {
            right = mid
        }
    }
    return result
}

func main() {
    s := "banana"
    fmt.Println(longestDupSubstring(s))
}

Algorithm

Использование двоичного поиска для определения длины дублированной подстроки:

Двоичный поиск используется для поиска максимальной длины дублированной подстроки.

Использование хеширования для проверки наличия дублированной подстроки определенной длины:

Для каждой длины, определенной двоичным поиском, используем хеширование для поиска подстрок.

Хеширование с помощью функции rolling hash:

Rolling hash позволяет быстро вычислять хеши подстрок фиксированной длины и сравнивать их для поиска дубликатов.

😎

Vacancies for this task

vagas ativas with overlapping task tags are mostradas.

Todas as vagas

Ainda não há vagas ativas.