Rearrange String


  • 2

    Given a string S, and an integer K, rearrange the string such that similar characters are at least K distance apart.

    Example:

    S = AAABBBCC, K = 3
    Result : ABCABCABC (all 'A's are 3 distance apart, similarly with B's and C's)

    S = AAABC, K=2 : Not possible. (EDIT : k=3 is not possible).

    S = AAADBBCC, K = 2:
    Result: ABCABCDA


  • 0

    I don't understand why example 2 is not valid. In my view S = ABACA is valid answer with K = 2, if ABCABCABC is valid for K = 3
    Store string characters in map by their frequency
    Deque the most frequent character and put it at position p, p+d,.. p+(f-1)d till n

    Here is possible implementation :

    public String rearrageString(String str, int d) throws Exception {
    	 		char[] res = new char[str.length()];	
    	 		Arrays.fill(res, '\0');  
    	 		Map<Character,Integer> freq = new HashMap<>();
    	 		for (char ch : str.toCharArray()) {
    	 			freq.put(ch,freq.containsKey(ch)?freq.get(ch)+1:1);
    	 		}
    	 		Queue<Character> pq = new PriorityQueue<>(new Comparator<Character>(){
    
    				@Override
    				public int compare(Character a, Character b) {
    					int aFreq = freq.containsKey(a)?freq.get(a):0;
    					int bFreq = freq.containsKey(b)?freq.get(b):0;
    					return bFreq - aFreq;
    				}
    	 			
    	 		});
    	 		pq.addAll(freq.keySet());
    	 		int p = 0;
    	 		while (!pq.isEmpty()) {
    	 			Character ch = pq.poll();
    	 			while (p < res.length && res[p]!='\0')
    	 				p++;
    	 			if(p == res.length)
    	 				throw new Exception("Invalid string");
    	 			int cnt = freq.get(ch);
    	 			int q = p;
    	 			while (q < res.length  && cnt > 0 ) {
    	 				res[q] = ch;
    	 				q+=d;
    	 			    cnt--;
    	 			}
    	 			if(cnt > 0)
    	 				throw new Exception("Invalid string");
    	 		}
    	 		return new String(res);
    	 	}

  • 0

    @elmirap Corrected it, thanks for pointing out..


  • 0

    @andyreadsall thank you


  • 0
    J

    @elmirap If string = aaabbcc and d = 2, your algorithm will not be working.


  • 2

    @jccg1000021953 right, the algorithm above works only if the same characters are at exact d characters apart.
    Here is a modification on it to take into account the "at least d" condition. The idea is the same with exception that when the last free slot is after the last position of the letter with maximum frequence, we start to insert characters from the beginning of the string at "d" distance.

    
    public  String rearrange(String s, int d) {  
    	    Map<Character, Integer> map = new HashMap<>();    
    	    int n = s.length();  
    	    for (int i=0; i < n; i++) {  
    	        Integer cnt = map.get(s.charAt(i));  
    	        if (cnt == null) 
    	        	cnt = 0;  
    	        map.put(s.charAt(i), cnt+1);  
    	    }  
    	    Queue<Character> queue = new PriorityQueue<>(map.size(), new Comparator<Character>(){  
    	        public int compare(Character c1, Character c2) {  
    	            return map.get(c2) - map.get(c1);  
    	        }  
    	    });  
    	    queue.addAll(map.keySet());  
    	    StringBuilder sb = new StringBuilder(n);
    	    int sz = n;
    	    while (sz > 0) {
    	    	sb.append('\0');
    	    	sz--;
    	    }
    	    
    	    int firstFree = 0;
    	    int m = map.get(queue.peek());
    	    while (!queue.isEmpty()) {
     			Character ch = queue.poll(); 			
     			while (firstFree < n && sb.charAt(firstFree) != '\0')
     				firstFree++; 	
     			int q = 0;
     			if (firstFree == n)
     				return "Cannot be rearranged";
     			if (firstFree < d*m - 1) {
     				q = firstFree; 	
     				firstFree++;
     			}
     			int cnt = map.get(ch); 			
     			while (q < n  && cnt > 0 ) {
     				if (sb.charAt(q) == '\0')
    	            	            sb.setCharAt(q, ch);
    	                        else
    	            	            sb.insert(q, ch);  
     				q+=d;
     			    cnt--;
     			}
     			if(cnt > 0)
     				return "Cannot be rearranged";
    
     		}	    
    	    return new String(sb.toString().substring(0, n));  
    	}

  • 0
    F

    Here's the algorithm I have in mind:

    1. Create a max heap of each character based on their number of occurence.
      Each node would be in the form {char, occurence, next} where next is initialized to 0 (represents the next index in the string at which it is legal to write it, initially every character can be the first one)

    2. Loop i from 0 to n, and at each iteration peak the highest-occurence and legal character. That is take the one with max occurence (possibly the root of our heap), but which "next" legal index is lower or equal to i

    3. Write this character and decrease its occurence by one, and update its next legal positon to i + K (because there need to be at least K letters in between this one and the next time we write it), then sift it down the heap if needed.

    Building the heap is O(n) and then each iteration is O(log n), which are done n times, so O(n log n) running time.


  • 0

    Here's my O(n) solution in C++:

    #include <string>
    #include <vector>
    #include <algorithm>
    #include <cassert>
    #include <iostream>
    
    using namespace std;
    
    class Solution {
    public:
      Solution() : size(0), pos(0) {}
    
      typedef pair<char, int> CharCount;
    
      vector<CharCount> count;
    
      int size; // how many chars in count to be output
    
      int pos; // pointer to count
    
      //Count frequency of chars, setting members count and size.
      void count_char(const string & s) {
        vector<int> frequency(26);
        for (int i = 0; i < s.size(); i++) {
          int idx = s[i] - 'A';
          assert(idx >= 0 && idx < frequency.size());
          frequency[idx]++;
        }
        for (int i = 0; i < frequency.size(); i++) {
          if (frequency[i] > 0) {
            count.push_back(make_pair('A' + i, frequency[i]));
          }
        }
        //Sort elements with bigger count before less one, so that they'll be output
        //in that order. See next_char();
        sort(count.begin(), count.end(), cmp);
        size = s.size();
      }
    
      //If there're more chars in count to output.
      bool has_more() {
        return size > 0;
      }
    
      //Output one char in count and reduce available size. The order matters.
      char next_char() {
        assert(pos < count.size() && size > 0 && count[pos].second > 0);
        char ret = count[pos].first;
        if (--count[pos].second == 0)
          ++pos;
        --size;
        return ret;
      }
    
      static bool cmp(const CharCount & a, const CharCount & b) {
        return (a.second > b.second) || (a.second == b.second && a.first < b.first);
      }
    
      string solve(const string & s, int k) {
        assert(k > 0);
    
        if (k > 26 || k >= s.size())
          return "";
    
        count_char(s);
    
        //Divide the chars into groups with k chars in each group, only the last
        //group may has less than k chars.
        int groups = s.size() / k;
        if (s.size() % k > 0)
          groups++;
    
        //If a char count is more than the number of groups, it means the char
        //must appear at least twice in one group and thus it's impossible to
        //ensure the distance k.
        for (int i = 0; i < count.size(); i++) {
          if (count[i].second > groups)
            return "";
        }
    
        vector<char> ret(s.size());
        int p = 0;
        while (has_more()) {
          assert(p < k);
          //Fill position p in each group with the next_char().
          for (int i = 0; i < groups && has_more(); i++) {
            int idx = i * k + p;
            if (idx >= ret.size())
              break;
            ret[idx] = next_char();
          }
          //Next position in each group to fill a char.
          p++;
        }
    
        return string(ret.begin(), ret.end());
      }
    };
    
    int main() {
      string s;
      int k;
      while (cin >> s >> k) {
        Solution so;
        string r = so.solve(s, k);
        if (r.empty())
          cout << "Impossible";
        else
          cout << r;
        cout << endl;
      }
      return 0;
    }
    

    The basic idea is to divide the chars from string s into n groups, each with k chars(only the last may has less than k chars). Then fill the position p(initially 0) of each group with the char of the most frequency, then the char of the less frequency and so on. When position p in each group is filled, ++p and repeat the procedure until all chars from s are filled in new container.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.