Determining whether a string is transformable into another by repetitively increasing its prefixes alphabetically 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 &lt;iostream&gt;

/*
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 -----&gt; so convertible (incrementing prefix bc)
*/
bool transformable(std::string&amp; A, std::string&amp; 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] &gt; B[last_index])
            {
                return false;
            }
            else
            {
                while(A[last_index] != B[last_index])
                {
                    for(int i = 0; i &lt;= last_index; i++)
                    {
                        A[i] += ('b' - 'a');
                    }
                }

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

        }

    }

}

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

    std::cin &gt;&gt; A &gt;&gt; B;

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

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

    return 0;
}
Code review

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


Missing #include &lt;string&gt;.
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 &lt;&lt; "YES\n";


instead of

std::cout &lt;&lt; "YES" &lt;&lt; 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 =&gt; 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 =&gt; bcdde =&gt; 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 &lt;algorithm&gt;
#include &lt;functional&gt;
#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;string_view&gt;
#include &lt;vector&gt;

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

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

    std::cin &gt;&gt; A &gt;&gt; B;

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


(live demo)

(Replace std::string_view with const std::string&amp; and remove the #include &lt;string_view&gt; 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&lt;&gt;{}),
            views::single(0)
        ), std::greater&lt;&gt;{});
}


(live demo)