HomeSoftware DevelopmentVariety of pairs of String whose concatenation results in a Sorted string

# 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.

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 = { 0 };

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

if (mark[i] == 1) {
int p = S[i] - '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 ans;
}

// Driver Code
int most important()
{

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

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

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

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

RELATED ARTICLES