Question

467. Unique Substrings in Wraparound String

中文文档

Description

We define the string base to be the infinite wraparound string of "abcdefghijklmnopqrstuvwxyz", so base will look like this:

• "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

Given a string s, return _the number of unique non-empty substrings of _s_ are present in _base.

 

Example 1:

Input: s = "a"
Output: 1
Explanation: Only the substring "a" of s is in base.

Example 2:

Input: s = "cac"
Output: 2
Explanation: There are two substrings ("a", "c") of s in base.

Example 3:

Input: s = "zab"
Output: 6
Explanation: There are six substrings ("z", "a", "b", "za", "ab", and "zab") of s in base.

 

Constraints:

• 1 <= s.length <= 105
• s consists of lowercase English letters.

Solutions

Solution 1

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 {
  public int findSubstringInWraproundString(String p) {
    int[] dp = new int[26];
    int k = 0;
    for (int i = 0; i < p.length(); ++i) {
      char c = p.charAt(i);
      if (i > 0 && (c - p.charAt(i - 1) + 26) % 26 == 1) {
        ++k;
      } else {
        k = 1;
      }
      dp[c - 'a'] = Math.max(dp[c - 'a'], k);
    }
    int ans = 0;
    for (int v : dp) {
      ans += v;
    }
    return ans;
  }
}

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
}

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()
  }
}