字符串处理

📌 核心概念

字符串贪心问题通常涉及字符重排、去重、拼接等操作，核心是利用贪心策略构造最优字符串。

贪心策略：优先处理频率最高的字符，或利用单调栈维护字典序。

💻 算法实现

🎯 经典应用

💡 解题技巧

📊 复杂度分析

问题	时间复杂度	空间复杂度	关键点
重构字符串	O(n log 26)	O(1)	堆+贪心
去除重复字母	O(n)	O(1)	单调栈
分割平衡字符串	O(n)	O(1)	计数器
最长快乐前缀	O(n)	O(n)	KMP
压缩字符串	O(n)	O(1)	双指针
字符串最大公因子	O(n+m)	O(n+m)	GCD
验证回文串II	O(n)	O(1)	双指针

Go 代码

import (
    "container/heap"
    "strings"
)
 
// 重构字符串
func reorganizeString(s string) string {
    freq := make(map[rune]int)
    maxFreq := 0
 
    for _, ch := range s {
        freq[ch]++
        if freq[ch] > maxFreq {
            maxFreq = freq[ch]
        }
    }
 
    if maxFreq > (len(s)+1)/2 {
        return ""
    }
 
    // 使用优先队列
    h := &MaxHeap{}
    heap.Init(h)
 
    for ch, count := range freq {
        heap.Push(h, &Item{char: ch, count: count})
    }
 
    result := []rune{}
    var prev *Item
 
    for h.Len() > 0 {
        item := heap.Pop(h).(*Item)
        result = append(result, item.char)
 
        if prev != nil && prev.count > 0 {
            heap.Push(h, prev)
        }
 
        item.count--
        prev = item
    }
 
    return string(result)
}
 
type Item struct {
    char  rune
    count int
}
 
type MaxHeap []*Item
 
func (h MaxHeap) Len() int           { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i].count > h[j].count }
func (h MaxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
 
func (h *MaxHeap) Push(x interface{}) {
    *h = append(*h, x.(*Item))
}
 
func (h *MaxHeap) Pop() interface{} {
    old := *h
    n := len(old)
    item := old[n-1]
    *h = old[0 : n-1]
    return item
}
 
// 去除重复字母
func removeDuplicateLetters(s string) string {
    count := make(map[rune]int)
    for _, ch := range s {
        count[ch]++
    }
 
    inStack := make(map[rune]bool)
    stack := []rune{}
 
    for _, ch := range s {
        count[ch]--
 
        if inStack[ch] {
            continue
        }
 
        for len(stack) > 0 && stack[len(stack)-1] > ch && count[stack[len(stack)-1]] > 0 {
            removed := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            delete(inStack, removed)
        }
 
        stack = append(stack, ch)
        inStack[ch] = true
    }
 
    return string(stack)
}

🎯 经典题目

题目	LeetCode	难度	关键点
重构字符串	767	中等	堆+贪心
去除重复字母	316	中等	单调栈
最小子序列	1081	中等	同316
分割平衡字符串	1221	简单	计数器
最长快乐前缀	1392	困难	KMP
压缩字符串	443	中等	双指针
字符串最大公因子	1071	简单	GCD
验证回文串II	680	简单	双指针

---

返回：贪心算法