Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/467.html

467. Unique Substrings in Wraparound String

Level

Medium

Description

Consider the string s to be the infinite wraparound string of “abcdefghijklmnopqrstuvwxyz”, so s will look like this: “…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd….”.

Now we have another string p. Your job is to find out how many unique non-empty substrings of p are present in s. In particular, your input is the string p and you need to output the number of different non-empty substrings of p in the string s.

Note: p consists of only lowercase English letters and the size of p might be over 10000.

Example 1:

Input: “a”

Output: 1

Explanation: Only the substring “a” of string “a” is in the string s.

Example 2:

Input: “cac”

Output: 2

Explanation: There are two substrings “a”, “c” of string “cac” in the string s.

Example 3:

Input: “zab”

Output: 6

Explanation: There are six substrings “z”, “a”, “b”, “za”, “ab”, “zab” of string “zab” in the string s.

Solution

If p has length 0, return 0.

Use an array counts with length 26 to store the number of unique substrings that ends with each letter. The first character in p (or p.charAt(0)) has an initial count of 1. Loop over p and compare each pair of adjacent characters. If the two adjacent characters differ by 1 (the two adjacent characters are “ab”, “bc”, “cd”, …, “xy”, “yz”, “za”), then the latter character has a count which is the previous count plus 1 (here “count” means the number of unique substrings that ends with the character). Otherwise, the latter character has a count 1. Update the character’s count to maintain its maximum count.

Finally, for each letter, obtain the number of unique substrings that ends with the letter. Calculate the sum and return.

• Java
• Python
• C++
• Go
• TypeScript
• RenderScript

• class Solution {
      public int findSubstringInWraproundString(String p) {
          if (p == null || p.length() == 0)
              return 0;
          int[] counts = new int[26];
          int length = p.length();
          counts[p.charAt(0) - 'a'] = 1;
          int prevCount = 1;
          for (int i = 1; i < length; i++) {
              char curC = p.charAt(i), prevC = p.charAt(i - 1);
              int curIndex = curC - 'a', prevIndex = prevC - 'a';
              int dif = (curIndex - prevIndex + 26) % 26;
              int curCount = dif == 1 ? prevCount + 1 : 1;
              counts[curIndex] = Math.max(counts[curIndex], curCount);
              prevCount = curCount;
          }
          int sum = 0;
          for (int count : counts)
              sum += count;
          return sum;
      }
  }
  

• class Solution:
      def findSubstringInWraproundString(self, p: str) -> int:
          dp = [0] * 26
          k = 0
          for i, c in enumerate(p):
              if i and (ord(c) - ord(p[i - 1])) % 26 == 1:
                  k += 1
              else:
                  k = 1
              idx = ord(c) - ord('a')
              dp[idx] = max(dp[idx], k)
          return sum(dp)
  
  ############
  
  class Solution(object):
    def findSubstringInWraproundString(self, p):
      """
      :type p: str
      :rtype: int
      """
      d = {}
      cnt = 0
      for i in range(len(p)):
        if i > 0 and (ord(p[i]) - ord(p[i - 1]) == 1 or ord(p[i - 1]) - ord(p[i]) == 25):
          cnt += 1
        else:
          cnt = 1
        d[ord(p[i])] = max(d.get(ord(p[i]), 0), cnt)
  
      return sum(d.values())
  
  

• class Solution {
  public:
      int findSubstringInWraproundString(string p) {
          vector<int> dp(26);
          int k = 0;
          for (int i = 0; i < p.size(); ++i) {
              char c = p[i];
              if (i && (c - p[i - 1] + 26) % 26 == 1)
                  ++k;
              else
                  k = 1;
              dp[c - 'a'] = max(dp[c - 'a'], k);
          }
          int ans = 0;
          for (int& v : dp) ans += v;
          return ans;
      }
  };
  

• func findSubstringInWraproundString(p string) int {
  	dp := make([]int, 26)
  	k := 0
  	for i := range p {
  		c := p[i]
  		if i > 0 && (c-p[i-1]+26)%26 == 1 {
  			k++
  		} else {
  			k = 1
  		}
  		dp[c-'a'] = max(dp[c-'a'], k)
  	}
  	ans := 0
  	for _, v := range dp {
  		ans += v
  	}
  	return ans
  }
  
  func max(a, b int) int {
  	if a > b {
  		return a
  	}
  	return b
  }
  

• function findSubstringInWraproundString(p: string): number {
      const n = p.length;
      const dp = new Array(26).fill(0);
      let cur = 1;
      dp[p.charCodeAt(0) - 'a'.charCodeAt(0)] = 1;
      for (let i = 1; i < n; i++) {
          if ((p.charCodeAt(i) - p.charCodeAt(i - 1) + 25) % 26 == 0) {
              cur++;
          } else {
              cur = 1;
          }
          const index = p.charCodeAt(i) - 'a'.charCodeAt(0);
          dp[index] = Math.max(dp[index], cur);
      }
      return dp.reduce((r, v) => r + v);
  }
  
  

• impl Solution {
      pub fn find_substring_in_wrapround_string(p: String) -> i32 {
          let n = p.len();
          let p = p.as_bytes();
          let mut dp = [0; 26];
          let mut cur = 1;
          dp[(p[0] - b'a') as usize] = 1;
          for i in 1..n {
              if (p[i] - p[i - 1] + 25) % 26 == 0 {
                  cur += 1;
              } else {
                  cur = 1;
              }
              let index = (p[i] - b'a') as usize;
              dp[index] = dp[index].max(cur);
          }
          dp.into_iter().sum()
      }
  }
  
  

All Problems

All Solutions