2022-04-07：给定一个只由'a'和'b'组成的字符串str， str中"ab"和"ba"子串都可以消除

2022-04-07：给定一个只由'a'和'b'组成的字符串str， str中"ab"和"ba"子串都可以消除， 消除之后剩下字符会重新靠在一起，继续出现可以消除的子串... 你的任务是决定一种消除的顺序，最后让str消除到尽可能的短。 返回尽可能的短的剩余字符串。 来自阿里。

答案2022-04-07：

方法一：栈。 方法二：分别求a和b的个数，然后做差，谁多输出谁。这个方法是我另外想的，经过大量测试，准确无误。 时间复杂度：O(N)。

代码用golang编写。代码如下：

package main

import (
	"fmt"
	"math/rand"
	"strings"
	"time"
)

func main() {
	rand.Seed(time.Now().UnixMilli())
	const TOTAL = 10000
	sucCount := 0
	for i := 0; i < TOTAL; i++ {
		s := getRandString()
		fmt.Println(s)
		ret1 := disappear3(s)
		fmt.Println("disappear3 = ", ret1)
		ret2 := disappear4(s)
		fmt.Println("disappear4 = ", ret2)
		if ret1 == ret2 {
			sucCount++
		}
		fmt.Println("---------------------")
	}
	fmt.Println("成功 = ", sucCount)
}

func disappear3(s string) string {
	str := []byte(s)
	n := len(str)
	// 用数组结构，自己实现栈
	stack := make([]int, n)
	size := 0
	for i := 0; i < n; i++ {
		hasA := size != 0 && str[stack[size-1]] == 'a'
		hasB := size != 0 && str[stack[size-1]] == 'b'
		hasA = hasA || str[i] == 'a'
		hasB = hasB || str[i] == 'b'
		if hasA && hasB {
			size--
		} else {
			stack[size] = i
			size++
		}
	}
	builder := make([]byte, 0)
	for i := 0; i < size; i++ {
		builder = append(builder, str[stack[i]])
	}
	return string(builder)
}

func disappear4(s string) string {
	n := len(s)
	acount := 0
	bcount := 0
	for i := 0; i < n; i++ {
		if s[i] == 'a' {
			acount++
		} else {
			bcount++
		}
	}

	if acount >= bcount {
		return strings.Repeat("a", acount-bcount)
	} else {
		return strings.Repeat("b", bcount-acount)
	}
}

func getRandString() string {
	n := 5 + rand.Intn(40)
	ret := make([]byte, n)
	for i := 0; i < n; i++ {
		aa := rand.Intn(2)
		if aa == 0 {
			ret[i] = 'a'
		} else {
			ret[i] = 'b'
		}
	}
	return string(ret)
}

执行结果如下：

左神java代码