PDD
昨天聊到 PDD 可能会执行双休政，当中提到了「PDD 的年包在互联网行业中名列前茅」，不少同学一下子来兴趣了。
我这里也从脉脉中找到一份较新的 PDD 各岗位薪资一览表：
注意，这里的平均月薪的计算方式是年收入除以 12，别忘了昨天我们提到的，拼多多普遍都是 15~16 薪（1~2个月的年终奖 + 1.5~2个月的加班费），海外组普遍是 16~18 薪。
因此，如果不考虑股票期权，想算一下真实的 base 是多少，大概将上述数字乘个 0.77 就差不多了（将 15.5 薪的年包等比折算回 12 薪）。
这里帮大家速算一些感兴趣的岗位：
C++：平均 base 约 40k
Java：平均 base 约 38k
前端：平均 base 约 30k
硬件：平均 base 约 28k
运维：平均 base 约 27k
数据分析：平均 base 约 27k
产品：平均 base 约 26k
由此可见，即使不算加班费，PDD 的 base 也属于有竞争力的一档。
大家还想看哪个厂的薪资一览，欢迎评论区留言。
...
回归主线。
来一道和「秋招」相关的算法原题。
题目描述
平台：LeetCode
题号：1763
当一个字符串 s 包含的每一种字母的大写和小写形式同时出现在 s 中，就称这个字符串 s 是美好字符串。
比方说，"abABB" 是美好字符串，因为 'A' 和 'a' 同时出现了，且 'B' 和 'b' 也同时出现了。
然而，"abA" 不是美好字符串因为 'b' 出现了，而 'B' 没有出现。
给你一个字符串 s ，请你返回 s 最长的美好子字符串。
如果有多个答案，请你返回最早出现的一个。如果不存在美好子字符串，请你返回一个空字符串。
示例 1：
输入：s = "YazaAay"输出："aAa"解释："aAa" 是一个美好字符串，因为这个子串中仅含一种字母，其小写形式 'a' 和大写形式 'A' 也同时出现了。"aAa" 是最长的美好子字符串。
示例 2：
输入：s = "Bb"输出："Bb"解释："Bb" 是美好字符串，因为 'B' 和 'b' 都出现了。整个字符串也是原字符串的子字符串。
示例 3：
输入：s = "c"输出：""解释：没有美好子字符串。
示例 4：
输入：s = "dDzeE"输出："dD"解释："dD" 和 "eE" 都是最长美好子字符串。由于有多个美好子字符串，返回 "dD" ，因为它出现得最早。
提示：
s 只包含大写和小写英文字母。
朴素解法
数据范围只有
，最为简单的做法是枚举所有的子串（ 复杂度为
），然后对子串进行合法性检查（ 复杂度为
），整体复杂度为
，可以过。
Java 代码：
class Solution { public String longestNiceSubstring(String s) { int n = s.length(); String ans = ""; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (j - i + 1 > ans.length() && check(s.substring(i, j + 1))) ans = s.substring(i, j + 1); } } return ans; } boolean check(String s) { Set
C++ 代码：
class Solution {public: string longestNiceSubstring(string s) { int n = s.length(); string ans = ""; for (int i = 0; i < n; i++) { for (int j = i + 1; j <= n; j++) { string sub = s.substr(i, j - i); if (j - i > ans.length() && check(sub)) ans = sub; } } return ans; } bool check(const string& s) { unordered_set
Python 代码：
class Solution: def longestNiceSubstring(self, s: str) -> str: n = len(s) ans = "" for i in range(n): for j in range(i + 1, n): if j - i + 1 > len(ans) and self.check(s[i:j+1]): ans = s[i:j+1] return ans def check(self, s): set_ = set() for c in s: set_.add(c) for c in s: a, b = c.lower(), c.upper() if a not in set_ or b not in set_: return False return True
时间复杂度：
空间复杂度：
前缀和优化
在 check 中，我们不可避免的遍历整个子串，复杂度为
。
该过程可以使用前缀和思想进行优化：「构建二维数组
来记录子串的词频，
为一个长度为
的数组，用于记录字符串 s 中下标范围为
的词频。即
所代表的含义为在子串
中字符
的出现次数。」
那么利用「容斥原理」，对于 s 的任意连续段
所代表的子串中的任意字符
的词频，我们可以作差算得：
这样我们在 check 实现中，只要检查
个字母对应的大小写词频（ASCII 相差
），是否同时为
或者同时不为
即可，复杂度为
。
Java 代码：
class Solution { public String longestNiceSubstring(String s) { int n = s.length(); int[][] cnt = new int[n + 1][128]; for (int i = 1; i <= n; i++) { char c = s.charAt(i - 1); cnt[i] = cnt[i - 1].clone(); cnt[i][c - 'A']++; } int idx = -1, len = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (j - i + 1 <= len) continue; int[] a = cnt[i], b = cnt[j + 1]; if (check(a, b)) { idx = i; len = j - i + 1; } } } return idx == -1 ? "" : s.substring(idx, idx + len); } boolean check(int[] a, int[] b) { for (int i = 0; i < 26; i++) { int low = b[i] - a[i], up = b[i + 32] - a[i + 32]; // 'A' = 65、'a' = 97 if (low != 0 && up == 0) return false; if (low == 0 && up != 0) return false; } return true; }}
C++ 代码：
class Solution {public: string longestNiceSubstring(string s) { int n = s.length(); vector
Python 代码：
class Solution: def longestNiceSubstring(self, s: str) -> str: n = len(s) cnt = [[0] * 128 for _ in range(n + 1)] for i in range(1, n + 1): c = s[i - 1] cnt[i] = cnt[i - 1].copy() cnt[i][ord(c) - ord('A')] += 1 idx, lenv = -1, 0 for i in range(n): for j in range(i + 1, n): if j - i + 1 <= lenv: continue if self.check(cnt[i], cnt[j + 1]): idx, lenv = i, j - i + 1 return "" if idx == -1 else s[idx: idx + lenv] def check(self, a, b): for i in range(26): low = b[i] - a[i] up = b[i + 32] - a[i + 32] if (low != 0 and up == 0) or (low == 0 and up != 0): return False return True
时间复杂度：令
为字符集大小，本题固定为
，构建
cnt 的复杂度为
；枚举所有子串复杂度为
；
check 的复杂度为
。整体复杂度为
空间复杂度：
二进制优化
更进一步，对于某个子串而言，我们只关心大小写是否同时出现，而不关心出现次数。
因此我们无须使用二维数组来记录具体的词频，可以在枚举子串时，使用两个 int 的低
位分别记录大小写字母的出现情况，利用枚举子串时右端点后移，维护两变量，当且仅当两变量相等时，满足
个字母的大小写同时出现或同时不出现。
Java 代码：
class Solution { public String longestNiceSubstring(String s) { int n = s.length(), idx = -1, len = 0; for (int i = 0; i < n; i++) { int a = 0, b = 0; for (int j = i; j < n; j++) { char c = s.charAt(j); if (c >= 'a' && c <= 'z') a |= (1 << (c - 'a')); else b |= (1 << (c - 'A')); if (a == b && j - i + 1 > len) { idx = i; len = j - i + 1; } } } return idx == -1 ? "" : s.substring(idx, idx + len); }}
C++ 代码：
class Solution {public: string longestNiceSubstring(string s) { int n = s.length(), idx = -1, len = 0; for (int i = 0; i < n; i++) { int a = 0, b = 0; for (int j = i; j < n; j++) { char c = s[j]; if (islower(c)) a |= (1 << (c - 'a')); else b |= (1 << (c - 'A')); if (a == b && j - i + 1 > len) { idx = i; len = j - i + 1; } } } return idx == -1 ? "" : s.substr(idx, len); }};
Python 代码：
class Solution: def longestNiceSubstring(self, s: str) -> str: n, idx, lenv = len(s), -1, 0 for i in range(n): a, b = 0, 0 for j in range(i, n): c = s[j] if c.islower(): a |= (1 << (ord(c) - ord('a'))) else: b |= (1 << (ord(c) - ord('A'))) if a == b and j - i + 1 > lenv: idx, lenv = i, j - i + 1 return "" if idx == -1 else s[idx: idx + lenv]
时间复杂度：
空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉