-1

Let's say you have the string cana. The string with the lexicographical order higher than that, would be cnaa. Is there any way you could do that, faster than just checking from right to left for every character?

smunteanu
  • 422
  • 3
  • 9
  • 1
    Please show your solution - you may have already found the best one. – 500 - Internal Server Error Mar 12 '21 at 18:22
  • 2
    Does this answer your question? [Algorithm to find next greater permutation of a given string](https://stackoverflow.com/questions/1622532/algorithm-to-find-next-greater-permutation-of-a-given-string) – jodag Mar 12 '21 at 18:46

1 Answers1

0
#include <string>
#include <algorithm>

void swap_chars(char &a, char &b) {
  char m = a;
  a = b;
  b = m;
}

std::string next(std::string str) {
  for (int i=str.length()-1; i>0; i--)
    if (str.at(i-1) < str.at(i)) {
      swap_chars(str.at(i-1), str.at(i));
      std::sort(str.begin()+i, str.end());
      break;
    }
  return str;
}
smunteanu
  • 422
  • 3
  • 9
  • 2
    If you're going to use `algorithm` you can just just use [`std::next_permutation(str.begin(), str.end())`](https://en.cppreference.com/w/cpp/algorithm/next_permutation). – jodag Mar 12 '21 at 19:17
  • @jodag I didn't know that. Thank you a lot – smunteanu Mar 12 '21 at 19:18