lhemakumar
diff --git a/‎solution/0400-0499/0467.Unique Substrings in Wraparound String/README.md
Lines changed: 60 additions & 68 deletions b/‎solution/0400-0499/0467.Unique Substrings in Wraparound String/README.md
Lines changed: 60 additions & 68 deletions
@@ -68,52 +68,48 @@ tags:
 
 ### 方法一：动态规划
 
-不妨设 `dp[α]` 表示 p 中以字符 α 结尾且在 s 中的子串的最大长度，将 dp 求和可以得到最终结果。
+我们不妨定义一个长度为 $26$ 的数组 $f$，其中 $f[i]$ 表示以第 $i$ 个字符结尾的最长连续子串的长度。那么答案就是 $f$ 中所有元素的和。
 
-时间复杂度 $O(n)$，其中 $n$ 表示字符串 p 的长度。
+我们定义一个变量 $k$，表示以当前字符结尾的最长连续子串的长度。遍历字符串 $s$，对于每个字符 $c$，如果 $c$ 和前一个字符 $s[i - 1]$ 之间的差值为 $1$，那么 $k$ 就加 $1$，否则 $k$ 重置为 $1$。然后更新 $f[c]$ 为 $f[c]$ 和 $k$ 的较大值。
 
-> 成为子串的一个标准，需要是连续的，`a` 与 `c` 之间少了一个 `b`，所以不能算一个子字符串。
+最后返回 $f$ 中所有元素的和即可。
+
+时间复杂度 $O(n)$，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O(|\Sigma|)$，其中 $\Sigma$ 是字符集，这里是小写字母集合。
 
 <!-- tabs:start -->
 
 #### Python3
 
 ```python
 class Solution:
-    def findSubstringInWraproundString(self, p: str) -> int:
-        dp = [0] * 26
+    def findSubstringInWraproundString(self, s: str) -> int:
+        f = defaultdict(int)
         k = 0
-        for i, c in enumerate(p):
-            if i and (ord(c) - ord(p[i - 1])) % 26 == 1:
+        for i, c in enumerate(s):
+            if i and (ord(c) - ord(s[i - 1])) % 26 == 1:
                 k += 1
             else:
                 k = 1
-            idx = ord(c) - ord('a')
-            dp[idx] = max(dp[idx], k)
-        return sum(dp)
+            f[c] = max(f[c], k)
+        return sum(f.values())
 ```
 
 #### Java
 
 ```java
 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) {
+    public int findSubstringInWraproundString(String s) {
+        int[] f = new int[26];
+        int n = s.length();
+        for (int i = 0, k = 0; i < n; ++i) {
+            if (i > 0 && (s.charAt(i) - s.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;
+            f[s.charAt(i) - 'a'] = Math.max(f[s.charAt(i) - 'a'], k);
         }
-        return ans;
+        return Arrays.stream(f).sum();
     }
 }
 ```
@@ -123,88 +119,84 @@ class Solution {
 ```cpp
 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)
+    int findSubstringInWraproundString(string s) {
+        int f[26]{};
+        int n = s.length();
+        for (int i = 0, k = 0; i < n; ++i) {
+            if (i && (s[i] - s[i - 1] + 26) % 26 == 1) {
                 ++k;
-            else
+            } else {
                 k = 1;
-            dp[c - 'a'] = max(dp[c - 'a'], k);
+            }
+            f[s[i] - 'a'] = max(f[s[i] - 'a'], k);
         }
-        int ans = 0;
-        for (int& v : dp) ans += v;
-        return ans;
+        return accumulate(begin(f), end(f), 0);
     }
 };
 ```
 
 #### Go
 
 ```go
-func findSubstringInWraproundString(p string) int {
-	dp := make([]int, 26)
+func findSubstringInWraproundString(s string) (ans int) {
+	f := [26]int{}
 	k := 0
-	for i := range p {
-		c := p[i]
-		if i > 0 && (c-p[i-1]+26)%26 == 1 {
+	for i := range s {
+		if i > 0 && (s[i]-s[i-1]+26)%26 == 1 {
 			k++
 		} else {
 			k = 1
 		}
-		dp[c-'a'] = max(dp[c-'a'], k)
+		f[s[i]-'a'] = max(f[s[i]-'a'], k)
 	}
-	ans := 0
-	for _, v := range dp {
-		ans += v
+	for _, x := range f {
+		ans += x
 	}
-	return ans
+	return
 }
 ```
 
 #### TypeScript
 
 ```ts
-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++;
+function findSubstringInWraproundString(s: string): number {
+    const idx = (c: string): number => c.charCodeAt(0) - 97;
+    const f: number[] = Array(26).fill(0);
+    const n = s.length;
+    for (let i = 0, k = 0; i < n; ++i) {
+        const j = idx(s[i]);
+        if (i && (j - idx(s[i - 1]) + 26) % 26 === 1) {
+            ++k;
         } else {
-            cur = 1;
+            k = 1;
         }
-        const index = p.charCodeAt(i) - 'a'.charCodeAt(0);
-        dp[index] = Math.max(dp[index], cur);
+        f[j] = Math.max(f[j], k);
     }
-    return dp.reduce((r, v) => r + v);
+    return f.reduce((acc, cur) => acc + cur, 0);
 }
 ```
 
 #### Rust
 
 ```rust
 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;
+    pub fn find_substring_in_wrapround_string(s: String) -> i32 {
+        let idx = |c: u8| -> usize { (c - b'a') as usize };
+        let mut f = vec![0; 26];
+        let n = s.len();
+        let s = s.as_bytes();
+        let mut k = 0;
+        for i in 0..n {
+            let j = idx(s[i]);
+            if i > 0 && ((j as i32) - (idx(s[i - 1]) as i32) + 26) % 26 == 1 {
+                k += 1;
             } else {
-                cur = 1;
+                k = 1;
             }
-            let index = (p[i] - b'a') as usize;
-            dp[index] = dp[index].max(cur);
+            f[j] = f[j].max(k);
         }
-        dp.into_iter().sum()
+
+        f.iter().sum()
     }
 }
 ```