2025-08-25：选择 K 个互不重叠的特殊子字符串。用go语言，给定长度为 n 的字符串 s 和整数 k，判断是否能从 s

package main

import (
    "fmt"
    "slices"
    "sort"
)

func maxSubstringLength(s string, k int)bool {
    if k == 0 { // 提前返回
        returntrue
    }

    // 记录每种字母的出现位置
    pos := [26][]int{}
    for i, b := range s {
        b -= 'a'
        pos[b] = append(pos[b], i)
    }

    // 构建有向图
    g := [26][]int{}
    for i, p := range pos {
        if p == nil {
            continue
        }
        l, r := p[0], p[len(p)-1]
        for j, q := range pos {
            if j == i {
                continue
            }
            k := sort.SearchInts(q, l)
            // [l,r] 包含第 j 个小写字母
            if k < len(q) && q[k] <= r {
                g[i] = append(g[i], j)
            }
        }
    }

    // 遍历有向图
    vis := [26]bool{}
    var l, r int
    var dfs func(int)
    dfs = func(x int) {
        vis[x] = true
        p := pos[x]
        l = min(l, p[0]) // 合并区间
        r = max(r, p[len(p)-1])
        for _, y := range g[x] {
            if !vis[y] {
                dfs(y)
            }
        }
    }

    intervals := [][2]int{}
    for i, p := range pos {
        if p == nil {
            continue
        }
        // 如果要包含第 i 个小写字母，最终得到的区间是什么？
        vis = [26]bool{}
        l, r = len(s), 0
        dfs(i)
        // 不能选整个 s，即区间 [0,n-1]
        if l > 0 || r < len(s)-1 {
            intervals = append(intervals, [2]int{l, r})
        }
    }

    return maxNonoverlapIntervals(intervals) >= k
}

// 435. 无重叠区间
// 直接计算最多能选多少个区间
func maxNonoverlapIntervals(intervals [][2]int) (ans int) {
    slices.SortFunc(intervals, func(a, b [2]int)int { return a[1] - b[1] })
    preR := -1
    for _, p := range intervals {
        if p[0] > preR {
            ans++
            preR = p[1]
        }
    }
    return
}

func main() {
    s := "abcdbaefab"
    k := 2
    result := maxSubstringLength(s, k)
    fmt.Println(result)
}

# -*-coding:utf-8-*-

def maxSubstringLength(s: str, k: int) -> bool:
    if k == 0:  # 提前返回
        return True
    
    n = len(s)
    # 记录每种字母的出现位置
    pos = [[] for _ in range(26)]
    for i, char in enumerate(s):
        idx = ord(char) - ord('a')
        pos[idx].append(i)
    
    # 构建有向图
    graph = [[] for _ in range(26)]
    for i in range(26):
        if not pos[i]:
            continue
        l_i = pos[i][0]
        r_i = pos[i][-1]
        for j in range(26):
            if j == i or not pos[j]:
                continue
            # 检查区间 [l_i, r_i] 是否包含第 j 个小写字母
            # 使用二分查找检查是否有 j 字母在区间内
            left, right = 0, len(pos[j]) - 1
            found = False
            while left <= right:
                mid = (left + right) // 2
                if pos[j][mid] < l_i:
                    left = mid + 1
                elif pos[j][mid] > r_i:
                    right = mid - 1
                else:
                    found = True
                    break
            if found:
                graph[i].append(j)
    
    # 遍历有向图
    visited = [False] * 26
    
    def dfs(x, current_l, current_r):
        visited[x] = True
        p = pos[x]
        new_l = min(current_l, p[0])
        new_r = max(current_r, p[-1])
        
        for y in graph[x]:
            if not visited[y]:
                new_l, new_r = dfs(y, new_l, new_r)
        
        return new_l, new_r
    
    intervals = []
    for i in range(26):
        if not pos[i]:
            continue
        
        # 重置visited
        visited = [False] * 26
        l_bound, r_bound = n, -1
        l_bound, r_bound = dfs(i, l_bound, r_bound)
        
        # 不能选整个s，即区间 [0, n-1]
        if l_bound > 0 or r_bound < n - 1:
            intervals.append((l_bound, r_bound))
    
    # 计算最多能选多少个不重叠区间
    if not intervals:
        return False
    
    # 按照区间右端点排序
    intervals.sort(key=lambda x: x[1])
    count = 0
    prev_r = -1
    
    for interval in intervals:
        if interval[0] > prev_r:
            count += 1
            prev_r = interval[1]
    
    return count >= k

# 测试代码
if __name__ == "__main__":
    s = "abcdbaefab"
    k = 2
    result = maxSubstringLength(s, k)
    print(result)  # 输出结果