Number of pairs of String whose concatenation leads to a Sorted string
#include <bits/stdc++.h>
using
namespace
std;
bool
sorted(string s)
{
for
(
int
i = 0; i < s.size() - 1; i++) {
if
(s[i] > s[i + 1])
return
false
;
}
return
1;
}
int
solve(string S[],
int
N)
{
bool
mark[N + 1] = { 0 };
for
(
int
i = 0; i < N; i++) {
if
(sorted(S[i])) {
mark[i] = 1;
}
}
int
nums[26] = { 0 };
for
(
int
i = 0; i < N; i++) {
if
(mark[i] == 1) {
int
p = S[i][0] -
'a'
;
nums[p] += 1;
}
}
int
ans = 0;
for
(
int
i = 0; i < N; i++) {
if
(mark[i] == 1) {
int
len = S[i].size();
int
last_char = S[i][len - 1] -
'a'
;
for
(
int
j = last_char; j < 26; j++) {
ans += nums[j];
}
}
}
return
ans;
}
int
main()
{
string S[] = {
"ac"
,
"df"
,
"pzz"
};
int
N =
sizeof
(S) /
sizeof
(S[0]);
cout << solve(S, N) << endl;
string S2[] = {
"pqrs"
,
"amq"
,
"bcd"
};
N =
sizeof
(S2) /
sizeof
(S2[0]);
cout << solve(S2, N) << endl;
return
0;
}
#include <bits/stdc++.h>
using
namespace
std;
bool
sorted(string s)
{
for
(
int
i = 0; i < s.size() - 1; i++) {
if
(s[i] > s[i + 1])
return
false
;
}
return
1;
}
int
solve(string S[],
int
N)
{
bool
mark[N + 1] = { 0 };
for
(
int
i = 0; i < N; i++) {
if
(sorted(S[i])) {
mark[i] = 1;
}
}
int
nums[26] = { 0 };
for
(
int
i = 0; i < N; i++) {
if
(mark[i] == 1) {
int
p = S[i][0] -
'a'
;
nums[p] += 1;
}
}
int
ans = 0;
for
(
int
i = 0; i < N; i++) {
if
(mark[i] == 1) {
int
len = S[i].size();
int
last_char = S[i][len - 1] -
'a'
;
for
(
int
j = last_char; j < 26; j++) {
ans += nums[j];
}
}
}
return
ans;
}
int
main()
{
string S[] = {
"ac"
,
"df"
,
"pzz"
};
int
N =
sizeof
(S) /
sizeof
(S[0]);
cout << solve(S, N) << endl;
string S2[] = {
"pqrs"
,
"amq"
,
"bcd"
};
N =
sizeof
(S2) /
sizeof
(S2[0]);
cout << solve(S2, N) << endl;
return
0;
}