Split String & Sort

Split an even-length string into two equal parts and sort them in ascending order.

Understand the Problem

Problem Statement

An even length string S is passed as the input. The program must split the string into two parts S1 and S2 and sort them in ascending order.

Constraints

2 ≤ Length of S ≤ 10000
The length of S is always even
S contains only printable ASCII characters

Examples

Example 1

Input

manage

Output

age
man

Explanation

The string "manage" has length 6, so it's split into S1 = "man" and S2 = "age". Sorting them alphabetically gives "age" and "man", which are printed on separate lines.

Example 2

Input

helloa

Output

aehl
lo

Explanation

The string "helloa" has length 6, so it's split into S1 = "hel" and S2 = "loa". Sorting them alphabetically gives "ehl" and "alo".

Solution

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

void sortString(char *str, int len) {
    for (int i = 0; i < len - 1; i++) {
        for (int j = 0; j < len - i - 1; j++) {
            if (str[j] > str[j + 1]) {
                char temp = str[j];
                str[j] = str[j + 1];
                str[j + 1] = temp;
            }
        }
    }
}

int main() {
    char S[10001];
    fgets(S, sizeof(S), stdin);
    
    int len = strlen(S);
    if (S[len - 1] == '\n') {
        S[len - 1] = '\0';
        len--;
    }
    
    int mid = len / 2;
    
    char S1[5001], S2[5001];
    strncpy(S1, S, mid);
    S1[mid] = '\0';
    strncpy(S2, S + mid, mid);
    S2[mid] = '\0';
    
    sortString(S1, mid);
    sortString(S2, mid);
    
    printf("%s\n%s\n", S1, S2);
    
    return 0;
}

Time:O(n²) where n is the length of each substring (due to bubble sort)

Space:O(n) for storing the two substrings

Approach:

Step-by-step explanation for C solution:

1. Reading Input: Uses fgets() to read the string and removes the trailing newline.

2. Calculating Midpoint: Finds the midpoint by dividing the string length by 2.

3. Splitting String: Uses strncpy() to copy the first half into S1 and the second half into S2.

4. Sorting: Implements bubble sort in the sortString() function to sort characters alphabetically.

5. Output: Prints both sorted substrings on separate lines.

Visual Explanation

Loading diagram...

All Problems