KK's blog

每天积累多一些

0%

LeetCode 761 Special Binary String

Posted on Disqus:

LeetCode

<div>

Special binary strings are binary strings with the following two properties:

  • The number of 0's is equal to the number of 1's.
  • Every prefix of the binary string has at least as many 1's as 0's.

You are given a special binary string s.

A move consists of choosing two consecutive, non-empty, special substrings of s, and swapping them. Two strings are consecutive if the last character of the first string is exactly one index before the first character of the second string.

Return the lexicographically largest resulting string possible after applying the mentioned operations on the string.

Example 1:

<pre>Input: s = "11011000" Output: "11100100" Explanation: The strings "10" [occuring at s[1]] and "1100" [at s[3]] are swapped. This is the lexicographically largest string possible after some number of swaps. </pre>

Example 2:

<pre>Input: s = "10" Output: "10" </pre>

Constraints:

  • 1 <= s.length <= 50
  • s[i] is either '0' or '1'.
  • s is a special binary string.

</div>

题目大意：

Special string由0和1组成，数目一样且每个前缀1的数目大于等于0的数目。可以交换其内部的子特别字符串，让其数值最大

解题思路：

一开始考虑用统计presum的方法LeetCode 696 Count Binary Substrings，然后如果后者1的数目大于前者0的数目，表示可以交换。但这里只考虑到相邻特别子串的关系，并没有考虑特别字串的内部也是需要排序的。

此题特别串是含有递归定义，所以考虑DFS。首先，一个特别字符串是由多个特别子串连续组成，所以需要找出它们，且进行排序
第二，更难的是每个字串内部特别字串也需要重新排序比如11011000中的10和1100就需要互换。这个串不是直接由内部特殊字串组成而是1+特殊串+0组成(递归式). 根据特殊串定义，是以1开头0结束，类似于统计左右括号数，这点规律比较难找。

总结而已，这题是catalan递归但不是递归两边是，多边。且每个递归都是由总结出来的规律获得1+f(s[start+1:i])获得

解题步骤：

N/A

注意事项：

  1. 如果遇到0，count要减一
  2. 倒序排序：parts.sort(reverse=True)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def makeLargestSpecial(self, s: str) -> str:
	parts = []
	count = 0
	start = 0
	for i in range(len(s)):
		if s[i] == '1':
			count += 1
		else:
			count -= 1 #attn
		if count == 0:
			sorted_part = '1'+ self.makeLargestSpecial(s[start+1:i]) + '0'
			parts.append(sorted_part)
			start = i + 1
	parts.sort(reverse=True) #attn
	return ''.join(parts)

算法分析：

next时间复杂度为O(n^2)，空间复杂度O(n)

错误的做法，只考虑到相互关系，没考虑内部关系

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def makeLargestSpecial(self, s: str) -> str:
	count, presum = 1, []
	for i in range(1, len(s)):
		if s[i] == s[i-1]:
			count += 1
		else:
			presum.append(count)
			count = 1
	if count > 0:
		presum.append(count)
	print(presum)

	def move(presum):
		is_moved = False
		for i in range(2, len(presum), 2):
			if presum[i] > presum[i-1]:
				presum[i-2] += -presum[i-1] + presum[i]
				presum[i+1] += -presum[i] + presum[i-1]
				presum[i-1], presum[i] = presum[i], presum[i-1]
				print(presum)
				is_moved = True
		return is_moved
	
	move_res = True
	while move_res:
		move_res = move(presum)

	res, c = '', '1'
	for n in presum:
		res += c * n
		if c == '1':
			c = '0'
		else:
			c = '1'
	print(res)
	return res

Free mock interview