Determining whether a string is transformable into another by repetitively increasing its prefixes alphabetically

Question

Here's Alice and Strings, a programming challenge on hackerearth:

Two strings \$A\$ and \$B\$ comprising of lower case English letters are compatible if they are equal or can be made equal by following this step any number of times:

• Select a prefix from the string \$A\$ (possibly empty), and increase the alphabetical value of all the characters in the prefix by the same valid amount. For example if the string is xyz and we select the prefix xy then we can convert it to yz by increasing the alphabetical value by 1. But if we select the prefix xyz then we cannot increase the alphabetical value.

Your task is to determine if given strings \$A\$ and \$B\$ are compatible.

Input format

First line: String \$A\$

Next line: String \$B\$

Output format

For each test case, print YES if string \$A\$ can be converted to string \$B\$, otherwise print NO.

Constraints

$$ \DeclareMathOperator{\len}{len} 1 \leq \len(A) \leq 1\,000\,000 \\ 1 \leq \len(B) \leq 1\,000\,000 \\ $$

Can you please review my solution to it? Please comment on any aspect to improve such as readability, comment usage, further improvements on speed/memory usage, etc.

/*
HackerEarth
https://www.hackerearth.com/practice/algorithms/string-algorithm/basics-of-string-manipulation/practice-problems/algorithm/aliceandstrings-9da62aa7/
*/

#include <iostream>

/*
Recusrsively checks if string A can be converted to B by incrementing the prefixes:

eg:
A = abaca B = cdbda
[step 1]bcbda (prefix abac incremented by 1)
[step 2]bc[b]da cd[b]da (don't take bcb as a prefix because b is already matched)
[step 3]cdbda -----> so convertible (incrementing prefix bc)
*/
bool transformable(std::string& A, std::string& B, int last_index)
{
    if (A.compare(0, last_index, B, 0, last_index) == 0)
    {
        return true;
    }
    else
    {
        if (A[last_index] == B[last_index])
        {
            return transformable(A, B, --last_index);
        }
        else
        {
            if (A[last_index] > B[last_index])
            {
                return false;
            }
            else
            {
                while(A[last_index] != B[last_index])
                {
                    for(int i = 0; i <= last_index; i++)
                    {
                        A[i] += ('b' - 'a');
                    }
                }

                return transformable(A, B, --last_index);
            }

        }

    }

}

int main()
{
    std::string A;
    std::string B;

    std::cin >> A >> B;

    if (A.length() != B.length())
    {
        std::cout << "NO" << std::endl;
        return 0;
    }

    if (transformable(A, B, A.length() - 1))
        std::cout << "YES" << std::endl;
    else
        std::cout << "NO" << std::endl;

    return 0;
}

Answer 1

Code review

In general, the code looks nice and follows consistent styles. Some small observations:

• Missing #include <string>.

• Avoid std::endl when \n suffices. std::endl flushes the buffer, while \n does not. Unnecessary flushing can cause performance degradation. See std::endl vs \n. Use

  std::cout << "YES\n";
  

  instead of

  std::cout << "YES" << std::endl;
  

  unless flushing is a requirement from the website (I hope not).

• Since we are depending on lowercase letters being continuously encoded anyway, 'B' - 'A' is just 1. And A[i] += 1 becomes ++A[i].

Better algorithm

That said, the logic of the code is overly convoluted. The many levels of nested control statements make it hard to follow the code. There is a much simpler algorithm to do it: to determine whether A is transformable into B,

• take the differences between the corresponding positions B[i] - A[i];

• form a sequence out of these differences;

• append the sequence by 0 (to prevent cases like bbbbb => aaaaa);

• test if this sequence is sorted in non-ascending order.

For example:

• for A = "abcde", B = "ccdde", the sequence of differences is 21100, so the transformation is possible (abcde => bcdde => ccdde);

• for A = "abcde", B = "bbcce", the sequence of differences is 10010, so the transformation is impossible (try it).

Here's (roughly) how I would put everything together:

#include <algorithm>
#include <functional>
#include <iostream>
#include <string>
#include <string_view>
#include <vector>

bool transformable(std::string_view a, std::string_view b)
{
    if (a.size() != b.size()) {
        return false;
    }
    std::vector<int> diff_sequence(a.size() + 1);
    std::transform(b.begin(), b.end(), a.begin(), diff_sequence.begin(), std::minus<>{});
    diff_sequence.back() = 0;
    return std::is_sorted(diff_sequence.begin(), diff_sequence.end(), std::greater<>{});
}

int main()
{
    std::string A;
    std::string B;

    std::cin >> A >> B;

    if (transformable(A, B)) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

(live demo)

(Replace std::string_view with const std::string& and remove the #include <string_view> if C++17 is not available, which IIRC is the case with competitive programming sites.)

The transformable function can be simplified with the range-v3 library:

namespace views = ranges::views;

bool transformable(std::string_view a, std::string_view b)
{
    return ranges::is_sorted(
        views::concat(
            views::transform(b, a, std::minus<>{}),
            views::single(0)
        ), std::greater<>{});
}

(live demo)