Generate string lexicographically larger than input

user_4224575 0
Viewed 114

Given an input string A, is there a concise way to generate a string B that is lexicographically larger than A, i.e. A < B == true?

My raw solution would be to say:

B = A;
++B.back();

but in general this won't work because:

  1. A might be empty
  2. The last character of A may be close to wraparound, in which case the resulting character will have a smaller value i.e. B < A.
  3. Adding an extra character every time is wasteful and will quickly in unreasonably large strings.

So I was wondering whether there's a standard library function that can help me here, or if there's a strategy that scales nicely when I want to start from an arbitrary string.

c++-standard-library c++ string
3 Answers

You can duplicate A into B then look at the final character. If the final character isn't the final character in your range, then you can simply increment it by one.

Otherwise you can look at last-1, last-2, last-3. If you get to the front of the list of chars, then append to the length.

user_13619010

Here is my dummy solution:

std::string make_greater_string(std::string const &input)
{
    std::string ret{std::numeric_limits<
                    std::string::value_type>::min()};
 
    if (!input.empty())
    {
        if (std::numeric_limits<std::string::value_type>::max() 
            == input.back())
        {
            ret = input + ret;
        }   
        else
        {   
            ret = input;
            ++ret.back();
        }   
    }
   
    return ret;
}

Ideally I'd hope to avoid the explicit handling of all special cases, and use some facility that can more naturally handle them. Already looking at the answer by @JosephLarson I see that I could increment more that the last character which would improve the range achievable without adding more characters.

And here's the refinement after the suggestions in this post:

std::string make_greater_string(std::string const &input)
{
    constexpr char minC = ' ', maxC = '~';
    // Working with limits was a pain, 
    // using ASCII typical limit values instead.
    
    std::string ret{minC};
 
    auto rit = input.rbegin(); 
    while (rit != input.rend())
    {
        if (maxC == *rit)
        {
            ++rit;
            if (rit == input.rend())
            {
                ret = input + ret;
                break;
            }
        }
        else
        {
            ret = input;
            ++(*(ret.rbegin() + std::distance(input.rbegin(), rit)));
            break;
        }
    }
   
    return ret;
}

Demo

user_42245750

You can copy the string and append some letters - this will produce a lexicographically larger result.

    B = A + "a"
user_171758010
Related