Welcome to Subscribe On Youtube

1044. Longest Duplicate Substring

Description

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 * 104
• s consists of lowercase English letters.

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      private long[] p;
      private long[] h;
  
      public String longestDupSubstring(String s) {
          int base = 131;
          int n = s.length();
          p = new long[n + 10];
          h = new long[n + 10];
          p[0] = 1;
          for (int i = 0; i < n; ++i) {
              p[i + 1] = p[i] * base;
              h[i + 1] = h[i] * base + s.charAt(i);
          }
          String ans = "";
          int left = 0, right = n;
          while (left < right) {
              int mid = (left + right + 1) >> 1;
              String t = check(s, mid);
              if (t.length() > 0) {
                  left = mid;
                  ans = t;
              } else {
                  right = mid - 1;
              }
          }
          return ans;
      }
  
      private String check(String s, int len) {
          int n = s.length();
          Set<Long> vis = new HashSet<>();
          for (int i = 1; i + len - 1 <= n; ++i) {
              int j = i + len - 1;
              long t = h[j] - h[i - 1] * p[j - i + 1];
              if (vis.contains(t)) {
                  return s.substring(i - 1, j);
              }
              vis.add(t);
          }
          return "";
      }
  }
  

• typedef unsigned long long ULL;
  
  class Solution {
  public:
      ULL p[30010];
      ULL h[30010];
      string longestDupSubstring(string s) {
          int base = 131, n = s.size();
          p[0] = 1;
          for (int i = 0; i < n; ++i) {
              p[i + 1] = p[i] * base;
              h[i + 1] = h[i] * base + s[i];
          }
          int left = 0, right = n;
          string ans = "";
          while (left < right) {
              int mid = (left + right + 1) >> 1;
              string t = check(s, mid);
              if (t.empty())
                  right = mid - 1;
              else {
                  left = mid;
                  ans = t;
              }
          }
          return ans;
      }
  
      string check(string& s, int len) {
          int n = s.size();
          unordered_set<ULL> vis;
          for (int i = 1; i + len - 1 <= n; ++i) {
              int j = i + len - 1;
              ULL t = h[j] - h[i - 1] * p[j - i + 1];
              if (vis.count(t)) return s.substr(i - 1, len);
              vis.insert(t);
          }
          return "";
      }
  };
  

• class Solution:
      def longestDupSubstring(self, s: str) -> str:
          def check(l):
              vis = set()
              for i in range(n - l + 1):
                  t = s[i : i + l]
                  if t in vis:
                      return t
                  vis.add(t)
              return ''
  
          n = len(s)
          left, right = 0, n
          ans = ''
          while left < right:
              mid = (left + right + 1) >> 1
              t = check(mid)
              ans = t or ans
              if t:
                  left = mid
              else:
                  right = mid - 1
          return ans
  
  

• func longestDupSubstring(s string) string {
  	base, n := 131, len(s)
  	p := make([]int64, n+10)
  	h := make([]int64, n+10)
  	p[0] = 1
  	for i := 0; i < n; i++ {
  		p[i+1] = p[i] * int64(base)
  		h[i+1] = h[i]*int64(base) + int64(s[i])
  	}
  	check := func(l int) string {
  		vis := make(map[int64]bool)
  		for i := 1; i+l-1 <= n; i++ {
  			j := i + l - 1
  			t := h[j] - h[i-1]*p[j-i+1]
  			if vis[t] {
  				return s[i-1 : j]
  			}
  			vis[t] = true
  		}
  		return ""
  	}
  	left, right := 0, n
  	ans := ""
  	for left < right {
  		mid := (left + right + 1) >> 1
  		t := check(mid)
  		if len(t) > 0 {
  			left = mid
  			ans = t
  		} else {
  			right = mid - 1
  		}
  	}
  	return ans
  }
  

All Problems

All Solutions