Make The String GreatLeetCode 1544多语言解法全解析从暴力扫描到栈与双指针【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文围绕 LeetCode 1544「Make The String Great」展开系统讲解如何移除字符串中相邻的坏字符对同一字母的大小写相邻如aA或Aa并给出暴力扫描、栈两种判定写法与原地双指针共四种解法的完整算法步骤、多语言代码实现与复杂度分析。读完本文你将掌握如何用栈模拟撤销相邻抵消这一经典模式并理解 ASCII 码差值32在大小写判断中的妙用能够直接把对应语言的实现运用于实际刷题场景。本文对应的完整思路文档见 articles/make-the-string-great.md仓库根目录 README.md 中按题目编号整理了各语言的题解入口方便横向对照学习。1. 问题背景与前置知识题目要求给定一个仅包含大小写英文字母的字符串s反复删除所有相邻的坏对——即同一字母、大小写不同且相邻的两个字符例如leEeetcode中eE是坏对删除后le与etcode拼接又可能产生新的坏对直到无法继续删除为止返回最终得到的字符串。动手解题前建议先具备以下三块基础能力栈数据结构用于高效追踪并移除相邻的坏对。栈天然支持后进先出正好契合相邻抵消、连锁反应的处理需求。ASCII 值ASCII 表中同一字母的大写与小写码值恰好相差32例如A为 65a为 97利用该性质可以快速判定坏对。字符串操作字符比较、按索引切片/删除、拼接结果字符串等基本操作。关键判定条件全文反复使用两个相邻字符构成坏对必须同时满足——字符本身不相同s[i] ! s[i-1]且忽略大小写后是同一字母lower(s[i]) lower(s[i-1])。只满足其一都不算坏对例如a与B虽不相同但不是同一字母不能删除。2. 解法一暴力扫描Brute Force直觉坏对由同一字母的不同大小写相邻组成如aA或Aa。暴力思路是反复扫描字符串寻找这样的配对一旦发现就删除这两个字符并从头附近重新扫描——因为删除一对后原本不相邻的字符可能变成相邻并构成新的坏对。算法步骤从索引0开始扫描字符串。在位置i检查当前字符与前一个字符是否构成坏对同一字母、不同大小写。若构成坏对删除这两个字符将i回退2以便重新检查删除后新相邻的字符并同步更新字符串长度n。持续扫描直到整串扫描完毕且不再出现坏对。返回处理后的字符串。多语言实现class Solution: def makeGood(self, s: str) - str: n len(s) i 0 while i n: if i and s[i] ! s[i - 1] and s[i].lower() s[i - 1].lower(): s s[:i - 1] s[i 1:] n - 2 i - 2 i 1 return spublic class Solution { public String makeGood(String s) { int n s.length(); int i 0; while (i n) { if (i 0 s.charAt(i) ! s.charAt(i - 1) Character.toLowerCase(s.charAt(i)) Character.toLowerCase(s.charAt(i - 1))) { s s.substring(0, i - 1) s.substring(i 1); n - 2; i - 2; } i; } return s; } }class Solution { public: string makeGood(string s) { int n s.length(); int i 0; while (i n) { if (i 0 s[i] ! s[i - 1] tolower(s[i]) tolower(s[i - 1])) { s s.substr(0, i - 1) s.substr(i 1); n - 2; i - 2; } i; } return s; } };class Solution { /** * param {string} s * return {string} */ makeGood(s) { let n s.length; let i 0; while (i n) { if ( i 0 s[i] ! s[i - 1] s[i].toLowerCase() s[i - 1].toLowerCase() ) { s s.slice(0, i - 1) s.slice(i 1); n - 2; i - 2; } i; } return s; } }public class Solution { public string MakeGood(string s) { int n s.Length; int i 0; while (i n) { if (i 0 s[i] ! s[i - 1] char.ToLower(s[i]) char.ToLower(s[i - 1])) { s s.Substring(0, i - 1) s.Substring(i 1); n - 2; i - 2; } i; } return s; } }func makeGood(s string) string { n : len(s) i : 0 for i n { if i 0 s[i] ! s[i-1] strings.ToLower(string(s[i])) strings.ToLower(string(s[i-1])) { s s[:i-1] s[i1:] n - 2 i - 2 } i } return s }class Solution { fun makeGood(s: String): String { var str s var n str.length var i 0 while (i n) { if (i 0 str[i] ! str[i - 1] str[i].lowercaseChar() str[i - 1].lowercaseChar()) { str str.substring(0, i - 1) str.substring(i 1) n - 2 i - 2 } i } return str } }class Solution { func makeGood(_ s: String) - String { var chars Array(s) var i 0 while i chars.count { if i 0 chars[i] ! chars[i - 1] chars[i].lowercased() chars[i - 1].lowercased() { chars.remove(at: i) chars.remove(at: i - 1) i - 2 } i 1 } return String(chars) } }impl Solution { pub fn make_good(s: String) - String { let mut s s.into_bytes(); let mut n s.len(); let mut i: isize 0; while (i as usize) n { let idx i as usize; if idx 0 s[idx] ! s[idx - 1] s[idx].to_ascii_lowercase() s[idx - 1].to_ascii_lowercase() { s.remove(idx); s.remove(idx - 1); n - 2; i - 2; } i 1; } String::from_utf8(s).unwrap() } }复杂度分析时间复杂度$O(n^2)$。每次删除都可能触发回退重扫最坏情况下如aAaA...这类交错大小写需要反复扫描。空间复杂度$O(n)$。字符串切片/重建会额外分配空间。3. 解法二栈Stack - I直觉栈天然处理撤销/抵消模式逐个处理字符每次将当前字符与栈顶比较。若构成坏对弹出栈顶等效于删除这两个字符否则入栈。栈结构自动处理连锁反应——新字符可能又和新的栈顶构成坏对无需回退索引。算法步骤初始化空栈用于构建结果。遍历字符串中的每个字符。对每个字符若栈非空且栈顶与当前字符构成坏对忽略大小写后是同一字母、但原字符不同则弹出栈顶。否则将当前字符压入栈。遍历结束后将栈内字符按顺序拼接成字符串返回。多语言实现class Solution: def makeGood(self, s: str) - str: def lower(c): if ord(c) ord(a): return chr(ord(a) ord(c) - ord(A)) return c stack [] i 0 while i len(s): if stack and stack[-1] ! s[i] and lower(stack[-1]) lower(s[i]): stack.pop() else: stack.append(s[i]) i 1 return .join(stack)public class Solution { public String makeGood(String s) { StringBuilder stack new StringBuilder(); for (char c : s.toCharArray()) { if (stack.length() 0 stack.charAt(stack.length() - 1) ! c Character.toLowerCase(stack.charAt(stack.length() - 1)) Character.toLowerCase(c)) { stack.deleteCharAt(stack.length() - 1); } else { stack.append(c); } } return stack.toString(); } }class Solution { public: string makeGood(string s) { string stack; for (char c : s) { if (!stack.empty() stack.back() ! c tolower(stack.back()) tolower(c)) { stack.pop_back(); } else { stack.push_back(c); } } return stack; } };class Solution { /** * param {string} s * return {string} */ makeGood(s) { const stack []; for (const c of s) { if ( stack.length 0 stack[stack.length - 1] ! c stack[stack.length - 1].toLowerCase() c.toLowerCase() ) { stack.pop(); } else { stack.push(c); } } return stack.join(); } }public class Solution { public string MakeGood(string s) { var stack new StringBuilder(); foreach (char c in s) { if (stack.Length 0 stack[stack.Length - 1] ! c char.ToLower(stack[stack.Length - 1]) char.ToLower(c)) { stack.Remove(stack.Length - 1, 1); } else { stack.Append(c); } } return stack.ToString(); } }func makeGood(s string) string { stack : []rune{} for _, c : range s { if len(stack) 0 stack[len(stack)-1] ! c unicode.ToLower(stack[len(stack)-1]) unicode.ToLower(c) { stack stack[:len(stack)-1] } else { stack append(stack, c) } } return string(stack) }class Solution { fun makeGood(s: String): String { val stack StringBuilder() for (c in s) { if (stack.isNotEmpty() stack.last() ! c stack.last().lowercaseChar() c.lowercaseChar()) { stack.deleteCharAt(stack.length - 1) } else { stack.append(c) } } return stack.toString() } }class Solution { func makeGood(_ s: String) - String { var stack [Character]() for c in s { if !stack.isEmpty stack.last! ! c stack.last!.lowercased() c.lowercased() { stack.removeLast() } else { stack.append(c) } } return String(stack) } }impl Solution { pub fn make_good(s: String) - String { let mut stack Vec::new(); for c in s.bytes() { if !stack.is_empty() *stack.last().unwrap() ! c stack.last().unwrap().to_ascii_lowercase() c.to_ascii_lowercase() { stack.pop(); } else { stack.push(c); } } String::from_utf8(stack).unwrap() } }补充说明Python 实现中手写了lower辅助函数利用 ASCII 关系大写字母码值小于a通过ord(c) - ord(A) ord(a)转为小写这是为了演示不依赖语言自带 API的纯 ASCII 判定实际刷题时直接使用str.lower()亦可。复杂度分析时间复杂度$O(n)$。每个字符最多入栈、出栈各一次。空间复杂度$O(n)$。栈最多容纳整个字符串。4. 解法三栈Stack - II利用 ASCII 差值 32直觉在 ASCII 中同一字母的大小写码值差恒为32a为 97A为 65z为 122Z为 90。因此若两个字符的 ASCII 码绝对差值等于32则它们必是同一字母的不同大小写——无需再分别做不同字符和忽略大小写相同两次判断一步到位。算法步骤初始化空栈。遍历字符串的每个字符若栈非空且当前字符与栈顶的 ASCII 绝对差值为32弹出栈顶否则将当前字符压入栈。返回栈内字符拼接成的字符串。多语言实现class Solution: def makeGood(self, s: str) - str: stack [] for i in range(len(s)): if stack and abs(ord(s[i]) - ord(stack[-1])) 32: stack.pop() else: stack.append(s[i]) return .join(stack)public class Solution { public String makeGood(String s) { StringBuilder stack new StringBuilder(); for (int i 0; i s.length(); i) { if (stack.length() 0 Math.abs(stack.charAt(stack.length() - 1) - s.charAt(i)) 32) { stack.deleteCharAt(stack.length() - 1); } else { stack.append(s.charAt(i)); } } return stack.toString(); } }class Solution { public: string makeGood(string s) { string stack; for (char c : s) { if (!stack.empty() abs(stack.back() - c) 32) { stack.pop_back(); } else { stack.push_back(c); } } return stack; } };class Solution { /** * param {string} s * return {string} */ makeGood(s) { const stack []; for (const c of s) { if ( stack.length 0 Math.abs( stack[stack.length - 1].charCodeAt(0) - c.charCodeAt(0), ) 32 ) { stack.pop(); } else { stack.push(c); } } return stack.join(); } }public class Solution { public string MakeGood(string s) { var stack new StringBuilder(); foreach (char c in s) { if (stack.Length 0 Math.Abs(stack[stack.Length - 1] - c) 32) { stack.Remove(stack.Length - 1, 1); } else { stack.Append(c); } } return stack.ToString(); } }func makeGood(s string) string { stack : []byte{} for i : 0; i len(s); i { if len(stack) 0 abs(int(stack[len(stack)-1])-int(s[i])) 32 { stack stack[:len(stack)-1] } else { stack append(stack, s[i]) } } return string(stack) } func abs(x int) int { if x 0 { return -x } return x }class Solution { fun makeGood(s: String): String { val stack StringBuilder() for (c in s) { if (stack.isNotEmpty() kotlin.math.abs(stack.last().code - c.code) 32) { stack.deleteCharAt(stack.length - 1) } else { stack.append(c) } } return stack.toString() } }class Solution { func makeGood(_ s: String) - String { var stack [Character]() for c in s { if !stack.isEmpty abs(Int(stack.last!.asciiValue!) - Int(c.asciiValue!)) 32 { stack.removeLast() } else { stack.append(c) } } return String(stack) } }impl Solution { pub fn make_good(s: String) - String { let mut stack Vec::new(); for b in s.bytes() { if !stack.is_empty() (*stack.last().unwrap() as i32 - b as i32).abs() 32 { stack.pop(); } else { stack.push(b); } } String::from_utf8(stack).unwrap() } }语言适配提示Go 需要自行实现abs辅助函数Rust 使用字节bytes()遍历天然以u8参与运算Swift 中asciiValue!仅对 ASCII 字符有效本题目保证输入只含英文字母因此安全。该解法只在输入为 ASCII 英文字母时成立若输入包含非英文字母字符则需退回解法二的通用大小写判定。复杂度分析时间复杂度$O(n)$。空间复杂度$O(n)$。5. 解法四原地双指针Two Pointers直觉不使用额外栈空间而是用双指针在原字符串上模拟栈左指针l表示虚拟栈的栈顶位置右指针r负责扫描输入。位置l之前的字符就是最终结果的前缀遇到坏对时通过l--实现弹出。算法步骤将字符串转为可变字符数组初始化l 0。从r 0遍历到末尾若l 0且位置r的字符与位置l - 1的字符构成坏对ASCII 差值32执行l--等效弹出坏对否则将位置r的字符复制到位置l然后l。返回索引0到l的子串。多语言实现class Solution: def makeGood(self, s: str) - str: l 0 s list(s) for r in range(len(s)): if l 0 and abs(ord(s[r]) - ord(s[l - 1])) 32: l - 1 else: s[l] s[r] l 1 return .join(s[:l])public class Solution { public String makeGood(String s) { int l 0; char[] arr s.toCharArray(); for (int r 0; r arr.length; r) { if (l 0 Math.abs(arr[r] - arr[l - 1]) 32) { l--; } else { arr[l] arr[r]; } } return new String(arr, 0, l); } }class Solution { public: string makeGood(string s) { int l 0; for (int r 0; r s.length(); r) { if (l 0 abs(s[r] - s[l - 1]) 32) { l--; } else { s[l] s[r]; } } return s.substr(0, l); } };class Solution { /** * param {string} s * return {string} */ makeGood(s) { let l 0; let arr s.split(); for (let r 0; r arr.length; r) { if ( l 0 Math.abs(arr[r].charCodeAt(0) - arr[l - 1].charCodeAt(0)) 32 ) { l--; } else { arr[l] arr[r]; } } return arr.slice(0, l).join(); } }public class Solution { public string MakeGood(string s) { int l 0; char[] arr s.ToCharArray(); for (int r 0; r arr.Length; r) { if (l 0 Math.Abs(arr[r] - arr[l - 1]) 32) { l--; } else { arr[l] arr[r]; } } return new string(arr, 0, l); } }func makeGood(s string) string { arr : []byte(s) l : 0 for r : 0; r len(arr); r { if l 0 abs(int(arr[r])-int(arr[l-1])) 32 { l-- } else { arr[l] arr[r] l } } return string(arr[:l]) } func abs(x int) int { if x 0 { return -x } return x }class Solution { fun makeGood(s: String): String { val arr s.toCharArray() var l 0 for (r in arr.indices) { if (l 0 kotlin.math.abs(arr[r].code - arr[l - 1].code) 32) { l-- } else { arr[l] arr[r] } } return String(arr, 0, l) } }class Solution { func makeGood(_ s: String) - String { var arr Array(s) var l 0 for r in 0..arr.count { if l 0 abs(Int(arr[r].asciiValue!) - Int(arr[l - 1].asciiValue!)) 32 { l - 1 } else { arr[l] arr[r] l 1 } } return String(arr[0..l]) } }impl Solution { pub fn make_good(s: String) - String { let mut arr s.into_bytes(); let mut l 0usize; for r in 0..arr.len() { if l 0 (arr[r] as i32 - arr[l - 1] as i32).abs() 32 { l - 1; } else { arr[l] arr[r]; l 1; } } arr.truncate(l); String::from_utf8(arr).unwrap() } }实现细节Rust 中arr.truncate(l)直接截断多余字符Go 通过arr[:l]切片返回Java/C#/Kotlin 则用new String(arr, 0, l)之类的构造方式取前缀。核心都在于让l之前的区域始终等于虚拟栈的内容。复杂度分析时间复杂度$O(n)$。单次线性扫描每个位置至多被读写一次。空间复杂度$O(1)$ 或 $O(n)$取决于语言。C/Go/Rust 可完全原地O(1)额外空间Java/Python/JavaScript 等因字符串不可变、需要字符数组如toCharArray()、list(s)、split()额外空间为 $O(n)$。6. 常见误区Common Pitfalls误区一只检查大小写不同却忽略同一字母坏对必须同时满足两个条件同一字母且大小写不同。如果只判断s[i] ! s[i-1]就会把a与B这类字符不同但并非同一字母的组合误判为坏对。必须额外验证忽略大小写后二者相等或使用 ASCII 差值32判定。误区二删除坏对后的索引回退量错误Off-by-One暴力扫描中删除一对字符后必须把索引回退2而不是 1才能重新检查删除后新相邻的两个字符。若错误地使用i - 1可能跳过删除动作产生的新坏对导致结果不正确。栈解法则天然规避了该问题因为弹出栈顶后下一轮比较的对象自动就是新的栈顶。7. 四种解法对比与实战选型解法核心思路时间空间适用场景暴力扫描反复扫描 删除 回退$O(n^2)$$O(n)$教学演示理解问题本质栈 - I栈顶与当前字符比较弹出/入栈$O(n)$$O(n)$通用写法任何字符集均可用栈 - II利用 ASCII 差值32判定$O(n)$$O(n)$输入仅含 ASCII 英文字母时的精简写法原地双指针用l模拟栈顶原地覆盖$O(n)$$O(1)$/$O(n)$追求最小额外空间的工程实现实战建议面试或刷题中优先掌握栈解法一思路直观、通用性最强随后理解解法四双指针以展示空间优化能力解法三的 ASCII 技巧适合作为面试时的亮点补充但需说明其 ASCII-only 的适用前提。8. 延伸思考这道题是相邻抵消 连锁反应类问题的典型代表栈模式的适用范围远不止于此。仓库中与之共享相同思维模型的题目还有remove-all-adjacent-duplicates-in-string-ii.md移除相邻重复字符的进阶版指定 k 个连续相同字符一并删除validate-parentheses.md括号配对抵消同样是栈顶匹配的经典场景minimum-remove-to-make-valid-parentheses.md删除最少字符使括号串合法栈 标记删除的结合。建议在 LeetCode 上以编号 1544 搜索原题自行验证各解法输入约束为1 s.length 100仅含大小写英文字母并配合本仓库 README.md 中的题目索引用多种语言反复练习直到能够在不借助文档的情况下独立写出栈解法与双指针解法。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考