2025高频面试算法总结篇【字符串】

---

直接刷题链接直达

1. 如何找出一个字符串中的最大不重复子串

• 3. 无重复字符的最长子串

2. 给定一个数，删除K位得到最小值

• 402. 移掉K位数字

3. 至多包含 K 个不同字符的最长子串

• 340. 至多包含 K 个不同字符的最长子串

4. 字符串的排列

• 面试题38. 字符串的排列
• 46. 全排列 （相同思路）

5. 至少有K个重复字符的最长子串

• 395. 至少有K个重复字符的最长子串

---

无重复字符的最长子串

题目： 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

思路：

• 滑动窗口 + 哈希表（Map） 解决问题

• start 只向前移动【start = Math.max(start, map.get(ch) + 1)】，保证 O(n) 复杂度

• 考虑边界情况（例如 “”, “bbbbb”, “abcd”）

import java.util.HashMap;
import java.util.Map;class Solution {public int lengthOfLongestSubstring(String s) {Map<Character, Integer> map = new HashMap<>(); // 存储字符和索引int maxLen = 0;int start = 0; // 滑动窗口左边界for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);// 如果字符重复，移动左边界（要取 `Math.max` 以保证 `start` 只向前移动）if (map.containsKey(ch)) {start = Math.max(start, map.get(ch) + 1);}// 更新最大长度maxLen = Math.max(maxLen, i - start + 1);// 记录当前字符的索引map.put(ch, i);}return maxLen;}
}

---

给定一个数，删除K位得到最小值

给你一个以字符串表示的非负整数 num 和一个整数 k ，移除这个数中的 k 位数字，使得剩下的数字最小。请你以字符串形式返回这个最小的数字。

关键点：

• 局部最优选择 -> 全局最优：
  尽量让前面的数字小，所以 遇到递增序列时，删除较大的数字。
• 使用单调栈：
  维护一个单调递增的栈，遇到比栈顶小的数字，就移除栈顶（减少较大的数字）。
• 去除前导 0：
  处理 000123 这样的情况，返回 “123” 而不是 “000123”。

思路：
使用 Stack<Character> 模拟递增序列，遍历 num：

• 遇到比栈顶小的数字，就移除栈顶（最多 k 次）。

• 所有数字入栈后，如果 k > 0，继续从栈顶移除剩余 k 个数字。

• 去除前导 0，避免 “000123” 这种情况。

import java.util.Stack;
class Solution {public String removeKdigits(String num, int k) {// 单调栈// （小->大）进栈，保持栈递增 高位越小越好if (num == null || num.length() <= k) return "0";Stack<Integer> stack = new Stack<>();for (int i = 0; i < num.length(); i++) {char ch = num.charAt(i);while (!stack.isEmpty() && k>0 && ch < num.charAt(stack.peek())) {stack.pop();k--;}stack.push(i);} while ( k>0) {stack.pop();k--;}// 去掉前导0StringBuilder sb = new StringBuilder();while(!stack.isEmpty()) {sb.append(num.charAt(stack.pop()));}sb.reverse();while(!sb.isEmpty() && sb.charAt(0) == '0') {sb.deleteCharAt(0);}return sb.isEmpty() ? "0":sb.toString();}
}

---

至多包含 K 个不同字符的最长子串

题目描述 ：给定一个字符串 s 和一个整数 k，找出 最多包含 k 个不同字符 的 最长子串 的长度。

解法： 滑动窗口 + 哈希表
核心思路：

• 维护一个滑动窗口 [left, right]，窗口内的子串最多包含 k 个不同字符。

• 用 HashMap<Character, Integer> 统计窗口内字符出现的次数：

• 当窗口内 字符种类 ≤ k：扩大窗口 right++。

• 当窗口内 字符种类 > k：缩小窗口 left++，直到字符种类恢复到 k。

• 记录窗口的最大长度。

import java.util.HashMap;
import java.util.Map;class Solution {public int lengthOfLongestSubstringKDistinct(String s, int k) {if (s.length() == 0 || k == 0) return 0;Map<Character, Integer> freqMap = new HashMap<>();int left = 0, maxLen = 0;for (int right = 0; right < s.length(); right++) {char ch = s.charAt(right);freqMap.put(ch, freqMap.getOrDefault(ch, 0) + 1);// 当窗口内的不同字符数超过 k，收缩左指针while (freqMap.size() > k) {char leftChar = s.charAt(left);freqMap.put(leftChar, freqMap.get(leftChar) - 1);if (freqMap.get(leftChar) == 0) {freqMap.remove(leftChar);}left++; // 缩小窗口}// 更新最大长度maxLen = Math.max(maxLen, right - left + 1);}return maxLen;}
}

---

字符串的排列

题目： 某店铺将用于组成套餐的商品记作字符串 goods，其中 goods[i] 表示对应商品。请返回该套餐内所含商品的 全部排列方式 。

返回结果 无顺序要求，但不能含有重复的元素。

class Solution {Set<String> ans = new HashSet<>();public String[] goodsOrder(String goods) {dfs(goods, new boolean[goods.length()], new StringBuilder());return ans.toArray(new String[0]);   }public void dfs(String goods, boolean[] used,StringBuilder res) {// 终止if (res.length() == goods.length()) {ans.add(res.toString());return;}//遍历for (int i = 0; i < goods.length(); i++) {if (!used[i]) {used[i] = true;res.append(goods.charAt(i));dfs(goods, used, res);// 回溯used[i] = false;res.deleteCharAt(res.length() - 1);}}}}

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

class Solution {Set<List<Integer>> ans = new HashSet<>();public List<List<Integer>> permute(int[] nums) {dfs(new ArrayList<>(), nums, new boolean[nums.length]);return new ArrayList<>(ans);}public void dfs(List<Integer> path, int[] nums, boolean[] used) {if (path.size() == nums.length) {ans.add(new ArrayList(path));return;}for (int i = 0; i < nums.length; i++) {if (!used[i]) {used[i] = true;path.add(nums[i]);dfs(path, nums, used);used[i] = false;path.remove(path.size() -1);}}}}

---

至少有K个重复字符的最长子串

题目： 给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

如果不存在这样的子字符串，则返回 0。

思路：

• 统计每个字符的频率

• 找到第一个不符合 k 的字符 ch

• 说明 以 ch 为中心切割，这个 ch 一定不会出现在最终结果中。

• 递归求解 ch 左边的子串和 ch 右边的子串，取最大值。

class Solution {public int longestSubstring(String s, int k) {// 找出 不符合 的字符// 双指针 剔除Map<Character, Integer> map = new HashMap<>();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);map.put(ch, map.getOrDefault(ch, 0) +1);}for (char ch : s.toCharArray()) {//找到第一个不符合 `k` 的字符if (map.get(ch) < k) {int maxLen = 0;// 以这个字符 `ch` 为分割点，递归求左右子串for (String sp : s.split(String.valueOf(ch))) {maxLen = Math.max(maxLen, longestSubstring(sp, k));}return maxLen;}}//如果所有字符都符合 k，返回整个字符串长度return s.length();}
}

---