Welcome to Subscribe On Youtube

767. Reorganize String

Description

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.

Return any possible rearrangement of s or return "" if not possible.

 

Example 1:

Input: s = "aab"
Output: "aba"

Example 2:

Input: s = "aaab"
Output: ""

 

Constraints:

• 1 <= s.length <= 500
• s consists of lowercase English letters.

Solutions

• Java
• C++
• Python
• Go
• RenderScript

• class Solution {
      public String reorganizeString(String s) {
          int[] cnt = new int[26];
          int mx = 0;
          for (char c : s.toCharArray()) {
              int t = c - 'a';
              ++cnt[t];
              mx = Math.max(mx, cnt[t]);
          }
          int n = s.length();
          if (mx > (n + 1) / 2) {
              return "";
          }
          int k = 0;
          for (int v : cnt) {
              if (v > 0) {
                  ++k;
              }
          }
          int[][] m = new int[k][2];
          k = 0;
          for (int i = 0; i < 26; ++i) {
              if (cnt[i] > 0) {
                  m[k++] = new int[] {cnt[i], i};
              }
          }
          Arrays.sort(m, (a, b) -> b[0] - a[0]);
          k = 0;
          StringBuilder ans = new StringBuilder(s);
          for (int[] e : m) {
              int v = e[0], i = e[1];
              while (v-- > 0) {
                  ans.setCharAt(k, (char) ('a' + i));
                  k += 2;
                  if (k >= n) {
                      k = 1;
                  }
              }
          }
          return ans.toString();
      }
  }
  

• class Solution {
  public:
      string reorganizeString(string s) {
          vector<int> cnt(26);
          for (char& c : s) ++cnt[c - 'a'];
          int mx = *max_element(cnt.begin(), cnt.end());
          int n = s.size();
          if (mx > (n + 1) / 2) return "";
          vector<vector<int>> m;
          for (int i = 0; i < 26; ++i) {
              if (cnt[i]) m.push_back({cnt[i], i});
          }
          sort(m.begin(), m.end());
          reverse(m.begin(), m.end());
          string ans = s;
          int k = 0;
          for (auto& e : m) {
              int v = e[0], i = e[1];
              while (v--) {
                  ans[k] = 'a' + i;
                  k += 2;
                  if (k >= n) k = 1;
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def reorganizeString(self, s: str) -> str:
          n = len(s)
          cnt = Counter(s)
          mx = max(cnt.values())
          if mx > (n + 1) // 2:
              return ''
          i = 0
          ans = [None] * n
          for k, v in cnt.most_common():
              while v:
                  ans[i] = k
                  v -= 1
                  i += 2
                  if i >= n:
                      i = 1
          return ''.join(ans)
  
  

• func reorganizeString(s string) string {
  	cnt := make([]int, 26)
  	for _, c := range s {
  		t := c - 'a'
  		cnt[t]++
  	}
  	mx := slices.Max(cnt)
  	n := len(s)
  	if mx > (n+1)/2 {
  		return ""
  	}
  	m := [][]int{}
  	for i, v := range cnt {
  		if v > 0 {
  			m = append(m, []int{v, i})
  		}
  	}
  	sort.Slice(m, func(i, j int) bool {
  		return m[i][0] > m[j][0]
  	})
  	ans := make([]byte, n)
  	k := 0
  	for _, e := range m {
  		v, i := e[0], e[1]
  		for v > 0 {
  			ans[k] = byte('a' + i)
  			k += 2
  			if k >= n {
  				k = 1
  			}
  			v--
  		}
  	}
  	return string(ans)
  }
  

• use std::collections::{ HashMap, BinaryHeap, VecDeque };
  
  impl Solution {
      #[allow(dead_code)]
      pub fn reorganize_string(s: String) -> String {
          let mut map = HashMap::new();
          let mut pq = BinaryHeap::new();
          let mut ret = String::new();
          let mut queue = VecDeque::new();
          let n = s.len();
  
          // Initialize the HashMap
          for c in s.chars() {
              map.entry(c)
                  .and_modify(|e| {
                      *e += 1;
                  })
                  .or_insert(1);
          }
  
          // Initialize the binary heap
          for (k, v) in map.iter() {
              if 2 * *v - 1 > n {
                  return "".to_string();
              } else {
                  pq.push((*v, *k));
              }
          }
  
          while !pq.is_empty() {
              let (v, k) = pq.pop().unwrap();
              ret.push(k);
              queue.push_back((v - 1, k));
              if queue.len() == 2 {
                  let (v, k) = queue.pop_front().unwrap();
                  if v != 0 {
                      pq.push((v, k));
                  }
              }
          }
  
          if ret.len() == n {
              ret
          } else {
              "".to_string()
          }
      }
  }
  
  

All Problems

All Solutions