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: 2Clarification: The pairs that kind a sorted string when concatenated are: {“aax”, “xz”}, {“bbc”, “xz”}

Enter: S[] = {“fg”, “mt”, “cd”}Output: 3Clarification: 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
s1is already unsorted ands2is any random string thens1 + s2won’t kind a sorted string.- If the final character of a string
s1is lesser than or equal to the primary character of one other strings2solely then the strings1 + s2could 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++

// 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: **