Variety of pairs of String whose concatenation results in a Sorted string

Given an array of strings S with the dimensions of N the place every string accommodates no less than two distinct characters. The duty is to seek out the variety of pairs of strings ( s[i], s[j] ) whose concatenation types a string that’s alphabetically sorted. Right here concatenation is solely the method of appending one string after one other.

Examples:

Enter: S[] = {“aax”, “bbc”, “xz”}
Output: 2
Clarification:  The pairs that kind a sorted string when concatenated are: {“aax”, “xz”}, {“bbc”, “xz”}

Enter: S[] = {“fg”, “mt”, “cd”}
Output: 3
Clarification: The pairs that kind a sorted string when concatenated are: {“cd”, “fg”}, {“cd”, “mt”}, {“fg”, “mt”}

Naive Method: The fundamental solution to remedy the issue is:

The brute power method for this drawback is to concatenate each pair of strings after which discover out if the string fashioned is sorted or not. 

Time complexity: O(N*N*max_size) the place N is the dimensions of the array of strings and max_size is the utmost measurement of the concatenation of two strings.
Auxiliary Area: O(1)

Environment friendly Method: A greater resolution relies on these information:

• If a string s1 is already unsorted and s2 is any random string then s1 + s2 won’t kind a sorted string.
• If the final character of a string s1 is lesser than or equal to the primary character of one other string s2 solely then the string s1 + s2 could be sorted (supplied each s1 and s2 are sorted).

Observe the below-mentioned steps to implement the above method:

• Initialize a boolean array mark[] and label solely these indexes as 1 for which s[i] is sorted and all different indexes as 0 (as to not take into account them later).
• For every alphabet (a-z), calculate the variety of sorted strings( mark[i] =1 ) that begin with that individual alphabet and retailer the rely in one other array ( say nums ).
• For every string s[i], retailer the final character of that string in some last_char variable. A string that begins with an alphabet that comes after or equal to last_char can get appended to s[i] and it’ll at all times kind a sorted string.
• Now iterate from the last_char until the final alphabet i.e. z and increment ans variable by the variety of strings ranging from every character concerned in iteration.
• Return the reply.

Beneath is the implementation of the above method:

// C++ implementation of program
#embrace <bits/stdc++.h>
utilizing namespace std;

// Examine if a selected string is
// sorted or not
bool sorted(string s)
{

    for (int i = 0; i < s.measurement() - 1; i++) {
        if (s[i] > s[i + 1])
            return false;
    }
    return 1;
}

// Perform to seek out the required
// variety of pairs
int remedy(string S[], int N)
{

    // Boolean array mark to think about solely
    // these strings that are sorted and
    // reject these which aren't sorted
    bool mark[N + 1] = { 0 };

    for (int i = 0; i < N; i++) {
        if (sorted(S[i])) {
            mark[i] = 1;
        }
    }
    // For each lower_case alphabet discover out
    // what number of strings begin with that
    // specific alphabet
    int nums[26] = { 0 };

    for (int i = 0; i < N; i++) {

        if (mark[i] == 1) {
            int p = S[i][0] - 'a';
            nums[p] += 1;
        }
    }

    // Compute the reply for all
    // the sorted strings
    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (mark[i] == 1) {
            int len = S[i].measurement();
            int last_char = S[i][len - 1] - 'a';

            for (int j = last_char; j < 26; j++) {
                ans += nums[j];
            }
        }
    }

    // Return the reply
    return ans;
}

// Driver Code
int most important()
{

    // Check case 1
    string S[] = { "ac", "df", "pzz" };
    int N = sizeof(S) / sizeof(S[0]);

    // Perform name
    cout << remedy(S, N) << endl;

    // Check case 2
    string S2[] = { "pqrs", "amq", "bcd" };
    N = sizeof(S2) / sizeof(S2[0]);

    // Perform name
    cout << remedy(S2, N) << endl;
    return 0;
}

Time Complexity: O(N*MAX_SIZE), MAX_SIZE is the size of longest string
Auxiliary Area: O(N)

Associated Articles: