1561. Rearrange Words In A Sentence¶

Difficulty: Medium

1561. Rearrange Words in a Sentence

Medium

Given a sentence text (A sentence is a string of space-separated words) in the following format:

First letter is in upper case.
Each word in text are separated by a single space.

Your task is to rearrange the words in text such that all words are rearranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.

Return the new text following the format shown above.

Example 1:

Input: text = "Leetcode is cool"
Output: "Is cool leetcode"
Explanation: There are 3 words, "Leetcode" of length 8, "is" of length 2 and "cool" of length 4.
Output is ordered by length and the new first word starts with capital letter.

Example 2:

Input: text = "Keep calm and code on"
Output: "On and keep calm code"
Explanation: Output is ordered as follows:
"On" 2 letters.
"and" 3 letters.
"keep" 4 letters in case of tie order by position in original text.
"calm" 4 letters.
"code" 4 letters.

Example 3:

Input: text = "To be or not to be"
Output: "To be or to be not"

Constraints:

text begins with a capital letter and then contains lowercase letters and single space between words.
1 <= text.length <= 10^5

Solution¶

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class Solution {
    static class Tuple {
        String s;
        int len, idx;
        public Tuple(String s, int len, int idx) {
            this.s = s;
            this.len = len;
            this.idx = idx;
        }
        @Override
        public String toString() {
            return "Pair{" +
                   "s='" + s + '\'' +
                   ", len=" + len +
                   ", idx=" + idx +
                   '}';
        }
    }

    static class customSort implements Comparator<Tuple> {
        @Override
        public int compare(Tuple first, Tuple second) {
            int op1 = Integer.compare(first.len, second.len);
            if (op1 != 0)
                return op1;
            return Integer.compare(first.idx, second.idx);
        }
    }

    public String arrangeWords(String text) {
        int n = text.length();
        ArrayList<Tuple> res = new ArrayList<>();
        String t = text + " ";
        StringBuilder sb = new StringBuilder();
        int currentIdx = 0;

        for (int i = 0; i < t.length(); i++) {
            if (t.charAt(i) == ' ') {
                res.add(new Tuple(sb.toString(), sb.toString().length(), currentIdx++));
                sb = new StringBuilder();
            } else
                sb.append(t.charAt(i));
        }

        Collections.sort(res, new customSort());
        StringBuilder ans = new StringBuilder();
        int stringIdx = 0;
        for (Tuple curr : res) {
            String current = curr.s;
            for (int i = 0; i < current.length(); i++) {
                if (i == 0 && stringIdx == 0)
                    ans.append(Character.toUpperCase(current.charAt(i)));
                else
                    ans.append(Character.toLowerCase(current.charAt(i)));
            }
            stringIdx++;
            if (stringIdx != res.size())
                ans.append(" ");
        }
        return ans.toString();
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here