Welcome to Subscribe On Youtube

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

  • 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;
    }
};

  • 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)


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

All Problems

All Solutions