Sort Strings by Length

63.9k
0

An array of strings words is given. Rearrange all strings in non-decreasing order of string length.

Equal-length strings must preserve original relative order. Return the sorted array.

Example 1

Input: words = ["pear", "a", "banana", "kiwi", "plum"]
Output: ["a", "pear", "kiwi", "plum", "banana"]
Explanation: String lengths are 4, 1, 6, 4, 4. The length order becomes 1, 4, 4, 4, 6, and equal-length strings pear, kiwi, and plum keep original order.

Example 2

Input: words = ["go"]
Output: ["go"]
Explanation: A single string already satisfies the required length order.

Brute Force Approach

The easiest observation is simple: each string only needs to move left past longer strings. Equal-length strings can stay in original order. Stable insertion follows exactly such movement.

A sorted prefix is maintained. The next string is saved, longer strings in the prefix move one position right, and the saved string enters the open position. Equal lengths never move past one another, so stability remains intact.

Algorithm

  • Begin with a copy named answer so the caller-owned array remains unchanged while the sorted result is built.

  • Keep the first string as a sorted prefix because a single element already satisfies non-decreasing length order.

  • Visit every later index from left to right so each pass extends the sorted prefix by one string.

  • Save the current string and start position at the preceding index so earlier strings can be checked from right to left.

  • Shift every longer prefix string one position right because the current string must appear before every longer value.

  • Place the saved string after the last shorter or equal-length string so equal lengths retain original relative order.

  • Return answer after every insertion because the complete array is then sorted stably by length.

Dry Run

Sort String By Length

Sort String By Length

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Sorts a copy through stable insertion.
vector<string> sortByLength(vector<string>& words) {
// Copying preserves the caller-owned array.
vector<string> answer = words;
int n = answer.size();
// Each pass extends the sorted prefix.
for (int index = 1; index < n; index++) {
// Saving prevents loss during right shifts.
string currentWord = answer[index];
int position = index - 1;
// Only longer strings move one place right.
while (position >= 0 &&
answer[position].size() > currentWord.size()) {
answer[position + 1] = answer[position];
position--;
}
// Equal lengths remain in original order.
answer[position + 1] = currentWord;
}
return answer;
}
};
// Driver code
int main() {
vector<string> words = {"pear", "a", "banana", "kiwi", "plum"};
Solution obj;
vector<string> answer = obj.sortByLength(words);
for (string value : answer) {
cout << value << " ";
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the number of strings, because each string can move across all earlier strings in the worst case.

Space Complexity: O(N), the copied result array stores all N strings.

Better Approach 1

String length is a non-negative integer, so each length can act as a direct bucket index. A small maximum length allows all strings to be grouped without pairwise comparisons.

Each string enters the matching bucket from left to right. Reading buckets from the smallest index to the largest index produces length order, while insertion order inside every bucket preserves stability. The method depends on a reasonably small maxLength value.

Algorithm

  • Scan words to find maxLength because the largest key determines the number of required buckets.

  • Build buckets for lengths from 0 through maxLength so every possible string length has a direct destination.

  • Visit strings from left to right because append order inside a bucket must match original relative order.

  • Use each string length as the bucket index so equal-length strings are grouped without comparisons.

  • Append every string to the matching bucket so stable order is recorded during the input scan.

  • Traverse buckets from length 0 through maxLength so shorter groups enter answer before longer groups.

  • Return answer after all buckets are drained because every string then appears in stable non-decreasing length order.

Dry Run

Sort String By Length Bucket Sort

Sort String By Length Bucket Sort

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Sorts a copy through length buckets.
vector<string> sortByLength(vector<string>& words) {
int maxLength = 0;
// The largest length sets the bucket count.
for (string& word : words) {
maxLength = max(maxLength, (int)word.size());
}
// Every possible length receives one bucket.
vector<vector<string>> buckets(maxLength + 1);
// Left-to-right appends preserve stable order.
for (string& word : words) {
int length = word.size();
buckets[length].push_back(word);
}
vector<string> answer;
// Shorter buckets must enter the answer first.
for (int length = 0; length <= maxLength; length++) {
for (string& word : buckets[length]) {
answer.push_back(word);
}
}
return answer;
}
};
// Driver code
int main() {
vector<string> words = {"pear", "a", "banana", "kiwi", "plum"};
Solution obj;
vector<string> answer = obj.sortByLength(words);
for (string value : answer) {
cout << value << " ";
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N + maxLength), all N strings enter one bucket and maxLength + 1 buckets are scanned.

Space Complexity: O(N + maxLength), the buckets and output array store all strings across the full length range.

Better Approach 2

Stable insertion can require many right shifts, especially with longer strings near the front. Merge sort reduces repeated movement by splitting the array into small ranges and joining sorted ranges in linear passes.

During each merge, string lengths are checked directly. The shorter string moves first, and the left string moves first for equal lengths. Selecting the left string on every length tie preserves the original relative order without a sorting callback.

Algorithm

  • Begin with a copied array named answer and a temporary array of equal size, so merging can rearrange strings without changing the caller-owned array.

  • Start merge sort on the complete index range because every string belongs to the final stable length order.

  • Stop a recursive call at a range containing at most one string because a single string already forms a sorted range.

  • Split every larger range at the middle index and sort both halves recursively, so each merge receives two ranges already ordered by length.

  • Compare the current string lengths from both halves and choose the left string on an equal length, so stable order survives every merge.

  • Move the chosen string into the temporary array and copy all remaining strings after one half finishes, so every string enters the merged range exactly once.

  • Copy the merged range back into answer, so completed ranges can support larger merges, and return answer after the complete range becomes sorted.

Dry Run

sort-string-by-length-better-approach

sort-string-by-length-better-approach

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Merges two ranges by string length.
void mergeRanges(vector<string>& answer,
vector<string>& temp,
int left, int middle, int right) {
int leftIndex = left;
int rightIndex = middle + 1;
int writeIndex = left;
// Current strings provide the next shortest value.
while (leftIndex <= middle && rightIndex <= right) {
// Equal lengths take the left string for stability.
if (answer[leftIndex].size() <=
answer[rightIndex].size()) {
temp[writeIndex] = answer[leftIndex];
leftIndex++;
} else {
temp[writeIndex] = answer[rightIndex];
rightIndex++;
}
writeIndex++;
}
// Remaining left strings keep sorted order.
while (leftIndex <= middle) {
temp[writeIndex] = answer[leftIndex];
leftIndex++;
writeIndex++;
}
// Remaining right strings keep sorted order.
while (rightIndex <= right) {
temp[writeIndex] = answer[rightIndex];
rightIndex++;
writeIndex++;
}
// The merged range replaces the old range.
for (int index = left; index <= right; index++) {
answer[index] = temp[index];
}
}
// Sorts one string range through merge sort.
void mergeSort(vector<string>& answer,
vector<string>& temp,
int left, int right) {
// A one-string range already has sorted order.
if (left >= right) {
return;
}
int middle = left + (right - left) / 2;
// Both halves become sorted before merging.
mergeSort(answer, temp, left, middle);
mergeSort(answer, temp, middle + 1, right);
// Two sorted halves form one sorted range.
mergeRanges(answer, temp, left, middle, right);
}
public:
// Sorts a copy through stable merge sort.
vector<string> sortByLength(vector<string>& words) {
vector<string> answer = words;
int n = answer.size();
vector<string> temp(n);
// A larger array needs recursive splitting.
if (n > 1) {
mergeSort(answer, temp, 0, n - 1);
}
return answer;
}
};
// Driver code
int main() {
vector<string> words = {"pear", "a", "banana", "kiwi", "plum"};
Solution obj;
vector<string> answer = obj.sortByLength(words);
for (string value : answer) {
cout << value << " ";
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), merge sort uses O(log N) levels and merges all N strings once per level.

Space Complexity: O(N), the temporary array stores N strings while the recursion stack uses O(log N) additional space.

Optimal Approach

The bucket method can be fast, but performance depends on a bounded maximum string length. No such restriction exists for the given string array, so allocating every length bucket can waste time and memory.

Stable comparison sorting works without a length bound. A comparator checks only string length, and stability keeps equal-length strings in original order. The approach provides O(n log n) time for unrestricted length values and becomes the optimal general solution.

Algorithm

  • Begin with a copy named answer so stable sorting produces a result without changing the caller-owned array.

  • Select a stable sorting routine because equal-length strings must preserve original relative order.

  • Compare only string lengths because lexicographical content has no role in the required ordering.

  • Pass C++ strings by reference inside the comparator so repeated comparisons avoid unnecessary string copies.

  • Place the shorter string first whenever lengths differ so the final order becomes non-decreasing by length.

  • Treat equal lengths as equivalent so the stable routine retains original order among tied strings.

  • Return answer after sorting because every string then satisfies both length order and stability.

Dry Run

Sort String by Length - Optimal Approach Comparator-v2

Sort String by Length - Optimal Approach Comparator-v2

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Sorts a copy with a stable length comparator.
vector<string> sortByLength(vector<string>& words) {
// Copying preserves the caller-owned array.
vector<string> answer = words;
// Read-only references avoid comparison copies.
stable_sort(
answer.begin(),
answer.end(),
[](const string& first, const string& second) {
return first.size() < second.size();
}
);
return answer;
}
};
// Driver code
int main() {
vector<string> words = {"pear", "a", "banana", "kiwi", "plum"};
Solution obj;
vector<string> answer = obj.sortByLength(words);
for (string value : answer) {
cout << value << " ";
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), stable comparison sorting performs logarithmic levels of comparisons across N strings.

Space Complexity: O(N), the copied result array and stable sorting support require linear auxiliary storage.

Interview follow-up Questions

Stable ordering removes ambiguity. For input ["pear", "kiwi", "plum"], all strings have length 4, so the stable answer remains ["pear", "kiwi", "plum"].

StringSorting

Read Similar Blogs

MathsTwo PointerSortingArraysBinary Search

Magnetic Force Between Two Balls

In the Magnetic Force Between Two Balls problem, you are given an integer array position representing the physical locations of various empty baskets on a number line. You are also given an integer...

82.5k
TrieRecursionArraysData StructuresString

Word Search II

Given a 2D board of characters and a list of words, return all words that can be formed on the board. Each word must be built by moving to horizontally or vertically adjacent cells. The same cell c...

100.8k
TrieSortingArraysData Structures

Search Suggestions System

Given an array of product names and a string searchWord , return the product suggestions after each character of searchWord is typed. For every prefix formed while typing, suggest at most three pro...

111k
Comments0