Rearrange a string so that all same characters become d distance away | GeeksforGeeks


Rearrange a string so that all same characters become d distance away | GeeksforGeeks

Related Leetcode - Given a string of lowercase characters, reorder them such that the same characters are at least distance d from each other.

Given a string and a positive integer d. Some characters may be repeated in the given string. Rearrange characters of the given string such that the same characters become (exactly) d distance away from each other.


Solution: The idea is to count frequencies of all characters and consider the most frequent character first and place all occurrences of it as close as possible. After the most frequent character is placed, repeat the same process for remaining characters.
1) Let the given string be str and size of string be n
2) Traverse str, store all characters and their frequencies in a Max Heap MH. The value of frequency decides the order in MH, i.e., the most frequent character is at the root of MH.
3) Make all characters of str as ‘\0′.
4) Do following while MH is not empty.
a) Extract the Most frequent character. Let the extracted character be x and its frequency be f.
b) Find the first available position in str, i.e., find the first ‘\0′ in str.
c) Let the first position be p. Fill x at p, p+d,.. p+(f-1)d

void rearrange(char str[], int d)
{
    // Find length of input string
    int n = strlen(str);
    // Create an array to store all characters and their
    // frequencies in str[]
    charFreq freq[MAX] = {{0, 0}};
    int m = 0; // To store count of distinct characters in str[]
    // Traverse the input string and store frequencies of all
    // characters in freq[] array.
    for (int i = 0; i < n; i++)
    {       
        char x = str[i];
        // If this character has occurred first time, increment m
        if (freq[x].c == 0)
            freq[x].c = x, m++;
        (freq[x].f)++;
        str[i] = '\0'// This change is used later
    }
    // Build a max heap of all characters
    buildHeap(freq, MAX);
    // Now one by one extract all distinct characters from max heap
    // and put them back in str[] with the d distance constraint
    for (int i = 0; i < m; i++)
    {
        charFreq x = extractMax(freq, MAX-i);
        // Find the first available position in str[]
        int p = i;
        while (str[p] != '\0')
            p++;
        // Fill x.c at p, p+d, p+2d, .. p+(f-1)d
        for (int k = 0; k < x.f; k++)
        {
            // If the index goes beyond size, then string cannot
            // be rearranged.
            if (p + d*k >= n)
            {
                cout << "Cannot be rearranged";
                exit(0);
            }
            str[p + d*k] = x.c;
        }
    }
}

Time Complexity: Time complexity of above implementation is O(n + mLog(MAX)). Here n is the length of str, m is count of distinct characters in str[] and MAX is maximum possible different characters. MAX is typically 256 (a constant) and m is smaller than MAX. So the time complexity can be considered as O(n).
More Analysis:
The above code can be optimized to store only m characters in heap, we have kept it this way to keep the code simple. So the time complexity can be improved to O(n + mLogm). It doesn’t much matter through as MAX is a constant.
Also, the above algorithm can be implemented using a O(mLogm) sorting algorithm. The first steps of above algorithm remain same. Instead of building a heap, we can sort the freq[] array in non-increasing order of frequencies and then consider all characters one by one from sorted array.
We will soon be covering an extended version where same characters should be moved at least d distance away.
http://yuanhsh.iteye.com/blog/2231105
Solution: The idea is to count frequencies of all characters and consider the most frequent character first and place all occurrences of it as close as possible. After the most frequent character is placed, repeat the same process for remaining characters.

Time Complexity: O(n+mlog(m)). Here n is the length of str, m is count of distinct characters in str[]. m is smaller than 256. So the time complexity can be considered as O(n).
  1. public static String rearrange(String str, int k) {  
  2.     Map<Character, Integer> map = new HashMap<>();  
  3.     char[] s = str.toCharArray();  
  4.     int n = s.length;  
  5.     for(int i=0; i<n; i++) {  
  6.         Integer cnt = map.get(s[i]);  
  7.         if(cnt == null) cnt = 0;  
  8.         map.put(s[i], cnt+1);  
  9.     }  
  10.     Queue<Character> queue = new PriorityQueue<>(map.size(), new Comparator<Character>(){  
  11.         public int compare(Character c1, Character c2) {  
  12.             return map.get(c2) - map.get(c1);  
  13.         }  
  14.     });  
  15.     queue.addAll(map.keySet());  
  16.     Arrays.fill(s, '\0');  
  17.     for(int i=0; i<map.size(); i++) {  
  18.         int p = i;  
  19.         while(s[p] != '\0') p++;  
  20.         char c = queue.poll();  
  21.         int cnt = map.get(c);  
  22.         for(int j=0; j<cnt; j++) {  
  23.             if(p >= n) return "Cannot be rearranged";  
  24.             s[p] = c;  
  25.             p += k;  
  26.         }  
  27.     }  
  28.     return new String(s);  
  29. }  


http://articles.leetcode.com/here-is-another-google-phone-interview/
The character that has the most duplicates has the highest priority of being chosen to put in the new list. If that character cannot be chosen (due to the distance constraint), we go for the character that has the next highest priority. We also use some tables to improve the efficiency. (i.e., keeping track of # of duplicates of each character.)

http://www.cnblogs.com/EdwardLiu/p/5140969.html
Not good implementation
FB面经Prepare task Schedule II很像,记录每个char出现次数,然后用最大堆,把剩下char里面出现次数多的优先Poll出来组建新的string
如果poll出来的char跟上一个相同,则用一个queue暂时存一下
我觉得时间复杂度:O(N) + O(KlogK) + O(NlogK) = O(NlogK) ,where K is the number of different character in the string
 5     class Element {
 6         char val;
 7         int appear;
 8         public Element(char value) {
 9             this.val = value;
10             this.appear = 1;
11         }
12     }
13     
14     public String reorder(String str) {
15         Element[] summary = new Element[26];
16         for (int i=0; i<str.length(); i++) {
17             char cur = str.charAt(i);
18             if (summary[(int)(cur-'a')] == null) {
19                 summary[(int)(cur-'a')] = new Element(cur);
20             }
21             else {
22                 summary[(int)(cur-'a')].appear++;
23             }
24         }
25         PriorityQueue<Element> queue = new PriorityQueue<Element>(11, new Comparator<Element>() {
26             public int compare(Element e1, Element e2) {
27                 return e2.appear - e1.appear;
28             }
29         });
30         
31         for (Element each : summary) {
32             if (each != null) {
33                 queue.offer(each);
34             }
35         }
36         Queue<Element> store = new LinkedList<Element>();
37         StringBuffer res = new StringBuffer();
38         while (!queue.isEmpty() || !store.isEmpty()) {
39             if (!queue.isEmpty()) {
40                 Element cur = queue.poll();
41                 if (res.length()==0 || cur.val!=res.charAt(res.length()-1)) {
42                     res.append(cur.val);
43                     cur.appear--;
44                     if (cur.appear > 0) store.offer(cur);
45                     while (!store.isEmpty()) {
46                         queue.offer(store.poll());
47                     }
48                 }
49                 else { //cur.val equals last char in res
50                     store.offer(cur);
51                 }
52             }
53             else { //store is not empty but queue is empty
54                 res = new StringBuffer();
55                 res.append(-1);
56                 return res.toString();
57             }
58         }
59         return res.toString();
60     }
Read full article from Rearrange a string so that all same characters become d distance away | GeeksforGeeks

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts