reorganize_string
1from collections import Counter 2 3 4# @leet start 5class Solution: 6 def reorganizeString(self, s: str) -> str: 7 """ 8 This question asks us to rearrange the characters of s so that no two 9 adjacent characters are the same. The way we do this is putting the 10 string into a counter, and making sure there's no majority element. 11 In the case that there is a majority element, there's no way to rearrange 12 the string such that no two adjacent characters are the same. 13 14 In the other case, we can solve the problem. We just need to iterate 15 through the string in most common order and then add to a string 16 every two places, starting at 0, and looping back to 1. This makes 17 it so no two adjacent characters will be the same. 18 """ 19 c = Counter(s) 20 n = len(s) 21 most_common_count = c.most_common(1)[0][1] 22 if n % 2 == 0 and most_common_count > n // 2: 23 return "" 24 if n % 2 == 1 and most_common_count > n // 2 + 1: 25 return "" 26 27 chars = [" "] * n 28 29 i = 0 30 31 for char, count in c.most_common(): 32 for _ in range(count): 33 chars[i] = char 34 if i + 2 < n: 35 i += 1 36 else: 37 i = 1 38 39 return "".join(chars) 40 41 42# @leet end 43 44 45def test(): 46 assert 2 + 2 == 4
class
Solution:
6class Solution: 7 def reorganizeString(self, s: str) -> str: 8 """ 9 This question asks us to rearrange the characters of s so that no two 10 adjacent characters are the same. The way we do this is putting the 11 string into a counter, and making sure there's no majority element. 12 In the case that there is a majority element, there's no way to rearrange 13 the string such that no two adjacent characters are the same. 14 15 In the other case, we can solve the problem. We just need to iterate 16 through the string in most common order and then add to a string 17 every two places, starting at 0, and looping back to 1. This makes 18 it so no two adjacent characters will be the same. 19 """ 20 c = Counter(s) 21 n = len(s) 22 most_common_count = c.most_common(1)[0][1] 23 if n % 2 == 0 and most_common_count > n // 2: 24 return "" 25 if n % 2 == 1 and most_common_count > n // 2 + 1: 26 return "" 27 28 chars = [" "] * n 29 30 i = 0 31 32 for char, count in c.most_common(): 33 for _ in range(count): 34 chars[i] = char 35 if i + 2 < n: 36 i += 1 37 else: 38 i = 1 39 40 return "".join(chars)
def
reorganizeString(self, s: str) -> str:
7 def reorganizeString(self, s: str) -> str: 8 """ 9 This question asks us to rearrange the characters of s so that no two 10 adjacent characters are the same. The way we do this is putting the 11 string into a counter, and making sure there's no majority element. 12 In the case that there is a majority element, there's no way to rearrange 13 the string such that no two adjacent characters are the same. 14 15 In the other case, we can solve the problem. We just need to iterate 16 through the string in most common order and then add to a string 17 every two places, starting at 0, and looping back to 1. This makes 18 it so no two adjacent characters will be the same. 19 """ 20 c = Counter(s) 21 n = len(s) 22 most_common_count = c.most_common(1)[0][1] 23 if n % 2 == 0 and most_common_count > n // 2: 24 return "" 25 if n % 2 == 1 and most_common_count > n // 2 + 1: 26 return "" 27 28 chars = [" "] * n 29 30 i = 0 31 32 for char, count in c.most_common(): 33 for _ in range(count): 34 chars[i] = char 35 if i + 2 < n: 36 i += 1 37 else: 38 i = 1 39 40 return "".join(chars)
This question asks us to rearrange the characters of s so that no two adjacent characters are the same. The way we do this is putting the string into a counter, and making sure there's no majority element. In the case that there is a majority element, there's no way to rearrange the string such that no two adjacent characters are the same.
In the other case, we can solve the problem. We just need to iterate through the string in most common order and then add to a string every two places, starting at 0, and looping back to 1. This makes it so no two adjacent characters will be the same.
def
test():