LeetCode Weekly Contest 456

func partitionString(s string) []string {
	segments := make([]string, 0)
	seen := make(map[string]bool)

	start := 0
	for i := 1; i <= len(s); i++ {
		segment := s[start:i]
		if !seen[segment] {
			seen[segment] = true
			segments = append(segments, segment)
			start = i
		}

	}
	return segments
}

package main

import (
	"fmt"
)

func lcp(a, b string) int {
	minLen := len(a)
	if len(b) < minLen {
		minLen = len(b)
	}
	for i := 0; i < minLen; i++ {
		if a[i] != b[i] {
			return i
		}
	}
	return minLen
}

func longestCommonPrefix(words []string) []int {
	n := len(words)
	ret := make([]int, n)
	if n <= 1 {
		return ret
	}

	// Step 1: 预处理所有相邻对的 LCP
	lcpPairs := make([]int, n-1)
	for i := 0; i < n-1; i++ {
		lcpPairs[i] = lcp(words[i], words[i+1])
	}

	// Step 2: 构建左区间最大值 & 右区间最大值数组
	leftPartMax := make([]int, n-1)
	rightPartMax := make([]int, n-1)

	leftPartMax[0] = lcpPairs[0]
	for i := 1; i < n-1; i++ {
		if lcpPairs[i] > leftPartMax[i-1] {
			leftPartMax[i] = lcpPairs[i]
		} else {
			leftPartMax[i] = leftPartMax[i-1]
		}
	}

	rightPartMax[n-2] = lcpPairs[n-2]
	for i := n - 3; i >= 0; i-- {
		if lcpPairs[i] > rightPartMax[i+1] {
			rightPartMax[i] = lcpPairs[i]
		} else {
			rightPartMax[i] = rightPartMax[i+1]
		}
	}

	// Step 3: 遍历每个被删除的 i
	for i := 0; i < n; i++ {
		maxLcp := 0
        // 处理好 i 的所有 case
		if i > 1 {
			maxLcp = leftPartMax[i-2]
		}
		if i+1 < n-1 {
			if rightPartMax[i+1] > maxLcp {
				maxLcp = rightPartMax[i+1]
			}
		}
		// 中间连接 i-1 和 i+1
		if i > 0 && i < n-1 {
			join := lcp(words[i-1], words[i+1])
			if join > maxLcp {
				maxLcp = join
			}
		}
		ret[i] = maxLcp
	}
	return ret
}

func main() {
	fmt.Println(longestCommonPrefix([]string{"jump", "run", "run", "jump", "run"}))                                               // [3 0 0 3 3]
	fmt.Println(longestCommonPrefix([]string{"dog", "racer", "car"}))                                                             // [0 0 0]
	fmt.Println(longestCommonPrefix([]string{"f", "cfe", "feab", "fcc", "cdfda", "fcec", "afae", "cdeb", "dc", "bffd", "edabe"})) //  [1,1,0,0,2,1,1,1,1,1,1]
}

	prefix := make([]int, n+1)
	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] ^ nums[i]
	}

	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, k+1)
		for j := range dp[i] {
			dp[i][j] = math.MaxInt32
		}
	}
	dp[0][0] = 0

	for i := 1; i <= n; i++ {
		for j := 1; j <= k && j <= i; j++ {
			for p := j - 1; p < i; p++ {
				x := prefix[i] ^ prefix[p]
				dp[i][j] = min(dp[i][j], max(dp[p][j-1], x))
			}
		}
	}

func minXor(nums []int, k int) int {
	n := len(nums)

	prefix := make([]int, n+1)
	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] ^ nums[i]
	}

	const inf = math.MaxInt32
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, k+1)
		for j := range dp[i] {
			dp[i][j] = inf
		}
	}
	dp[0][0] = 0

	for i := 1; i <= n; i++ {
		for j := 1; j <= k && j <= i; j++ {
			for p := j - 1; p < i; p++ {
				x := prefix[i] ^ prefix[p]
				dp[i][j] = min(dp[i][j], max(dp[p][j-1], x))
			}
		}
	}

	return dp[n][k]
}

func xorQueries(arr []int, queries [][]int) []int {
	n := len(arr)
	prefix := make([]int, n+1)

	for i := 0; i < n; i++ {
		prefix[i+1] = prefix[i] ^ arr[i]
	}

	ret := make([]int, len(queries))

	for i, query := range queries {
		start:= query[0]
		end := query[1]
		ret[i] = prefix[start] ^ prefix[end+1]
	}

	return ret
}