Java C++ 算法leetcode828统计子串中唯一字符乘法原理

题目要求

思路：模拟

解题的核心思想在于逆向思维，不考虑每个子数组中的唯一字符个数，转而考虑每个字符可以作为多少个子数组的唯一字符；

• 所以在计算答案时的算式和示例中给出的是不一样的；

• 在计算每个字符“贡献”【即当前向左向右分别可组成的答案个数】的时候要用到乘法原理。

对每一个字符s[i]s[i]s[i]都记录其左边和右边的第一个相同字符位置，分别记为l[i]l[i]l[i]和r[i]r[i]r[i]，这两个位置中间构成的就是s[i]s[i]s[i]能够作为唯一字符的最长子串，在这个最长的子串中还有若干个较短的子串，此时s[i]s[i]s[i]的“贡献”可由到左边和到右边的距离相乘计算得出。

java

class Solution {
   public int uniqueLetterString(String s) {
       char[] cs = s.toCharArray();
       int n = cs.length, res = 0;
       int[] l = new int[n], r = new int[n];
       int[] letters = new int[26];
       Arrays.fill(letters, -1);
       for (int i = 0; i < n; i++) {
           int idx = cs[i] - 'A';
           l[i] = letters[idx]; // 左边第一个相同的字符所在位置
           letters[idx] = i; // 更新当前字母最新左位置
       }
       Arrays.fill(letters, n);
       for (int i = n - 1; i >= 0; i--) {
           int idx = cs[i] - 'A';
           r[i] = letters[idx]; // 右边第一个相同的字符所在位置
           letters[idx] = i; // 更新当前字母最新右位置
       }
       for (int i = 0; i < n; i++)
           res += (i - l[i]) * (r[i] - i);
       return res;
   }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)

C++

• 因为memset初始化问题，所以在构成结果的时候多一步判断。

class Solution {
public:
   int uniqueLetterString(string s) {
       int n = s.size(), res = 0;
       cout << n << endl;
       int l[n], r[n];
       int letters[26];
       memset(letters, -1, sizeof(letters));
       for (int i = 0; i < n; i++) {
           int idx = s[i] - 'A';
           l[i] = letters[idx]; // 左边第一个相同的字符所在位置
           letters[idx] = i; // 更新当前字母最新左位置
       }
       memset(letters, -1, sizeof(letters));
       for (int i = n - 1; i >= 0; i--) {
           int idx = s[i] - 'A';
           r[i] = letters[idx]; // 右边第一个相同的字符所在位置
           letters[idx] = i; // 更新当前字母最新右位置
       }
       for (int i = 0; i < n; i++) {
           int ri = r[i] == -1 ? n : r[i];
           res += (i - l[i]) * (ri - i);
       }
       return res;
   }
};

• 时间复杂度：O(n)

• 空间复杂度：O(n)

Rust

• 用Rust的遍历稍微改一下，思路一样&hellip;&hellip;

impl Solution {
   pub fn unique_letter_string(s: String) -> i32 {
       let cs = s.as_bytes();
       (0..s.len()).into_iter().map(|i| {
           let (mut l, mut r) = (i - 1, i + 1);
           while l < s.len() && cs[l] != cs[i] {
               l -= 1;
           }
           while r < s.len() && cs[r] != cs[i] {
               r += 1;
           }
           ((i - l) * (r - i)) as i32
       }).sum::<i32>()
   }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)

来源：https://juejin.cn/post/7140264367676719117