Finding next lexicographic largest permutation of a string - C++

Question

I was working on one of the Hackerrank programs, Bigger is Greater, and it basically deals with finding the next largest lexicocraphic permutation of a string. I've implemented my solution, following an algorithm described here. I then store all the permutations in a vector, loop through it, and search for the next permutation after my original word, since this algorithm builds the permutations in sorted order.

This works for small inputs, however, as the problem scales to large inputs (long words), it becomes un-runnable. I'm wondering if there's a better approach to this, that still uses the recursive algorithm I've implemented (since it makes sense to me).

#include <map>
#include <cmath>
#include <string>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

/**
 * [check_args description]
 * @param  t [description]
 * @param  w [description]
 * @return   [description]
 */
bool check_args(int t, int w) {
    if(t < 1 || t > 100000) {
        return false;
    }
    if(abs(w) < 0 || abs(w) > 100) {
        return false;
    }
    return true;
}

/**
 * [print_array description]
 * @param size [description]
 * @param arr  [description]
 */
void print_array(int size, string *arr) {
    for(int i = 0; i < size; i++) {
        cout << arr[i] << endl;
    }
}

/**
 * [print_array description]
 * @param size [description]
 * @param arr  [description]
 */
void print_array(int size, char *arr) {
    for(int i = 0; i < size; i++) {
        cout << arr[i];
    }
    cout << endl;
}

/**
 * [print_map description]
 * @param m [description]
 */
void print_map(map<char, int> m) {
    for(map<char,int>::const_iterator it = m.begin(); it != m.end(); ++it) {
        cout << it->first << " " << it->second << endl;
    }
}

/**
 * [permutation_util description]
 * @param str    [description]
 * @param count  [description]
 * @param result [description]
 * @param level  [description]
 * RECURSIVE
 */
void permutation_util(char *str, int *count, char *result, 
                            int string_length, int result_length, 
                            int level, vector<string> *acc) {
    if(result_length == level) {
        acc->push_back(result);
        return;
    }
    for(int i = 0; i < string_length; i++) {
        if(count[i] != 0) {
            // Continue through with recursion
            result[level] = str[i]; // Store the char in the current level of recursion
            count[i]--; // We used a char, so decrement the count
            permutation_util(str, count, result, string_length, result_length, level + 1, acc);
            count[i]++;
        }
    }
}

/**
 * [permutation description]
 * @param length [description]
 * @param word   [description]
 * @param result [description]
 */
vector<string> * permutation(string word) {
    map<char, int> occurences;
    // Populate map
    for(int i = 0; i < word.length(); i++) {
        if(occurences.count(word[i]) == 0) {
            occurences[word[i]] = 1;
        }
        else {
            occurences[word[i]]++;
        }
    }
    char *str = new char[occurences.size()];
    int *count = new int[occurences.size()];
    int index = 0;
    /*
     * Build string and counts in the following format:
     * Original String: A A B C
     * New String (str): A B C
     *                   | | |
     * New Count  (int): 2 1 1
     *
     * Where chars are mapped to number of occurences
     */
    for(map<char,int>::const_iterator it = occurences.begin(); it != occurences.end(); ++it) {
        str[index] = it->first;
        count[index] = it->second;
        index++;
    }
    char *result = new char[word.length()];
    int result_length = word.length();
    int string_length = occurences.size();
    // Accumulator to store permutations
    vector<string> *acc = new vector<string>();
    // Recursive call
    permutation_util(str, count, result, string_length, result_length, 0, acc);
    return acc;
}

void find_lexicographically_bigger(string word, vector<string> * perms) {
    /* 
     * If the only perm was itself, we know there's nothing that
     * could be lexicographically bigger
     */
    if(perms->size() == 1) {
        cout << "no answer" << endl;
        return;
    }
    /*
     * Loop through and find the next greatest word after
     * the input
     */
    for(int i = 0; i < perms->size(); i++) {
        if(perms->at(i) == word) {
            // Get next largest
            cout << perms->at(i + 1) << endl;
            return;
        }
    }
}

int main() {
    int test_cases = 0;
    cin >> test_cases;
    string *words = new string[test_cases];

    // For each test case, gather our words
    for(int i = 0; i < test_cases; i++) {
        string w;
        cin >> w;
        words[i] = w;
        if(!check_args(test_cases, w.length())) {
            return 1;
        }
    }
    // For each word, run the algorithm
    for(int i = 0; i < test_cases; i++) {
        // Find the next largest word
        string word = words[i];
        if(word.length() == 1) {
            cout << "no answer" << endl;
        }
        else {
            find_lexicographically_bigger(word, permutation(word));
        }
    }
    return 0;
}

Answer 1

C style arrays and Raw Pointers

string *words = new string[test_cases];

Try not to do this often. If you are programming in C++, you should try to stick to C++ as much as possible and you will find that it is quite capable of handling a lot of what you need. C++ is more object oriented than C is, and as such it also provides you with generic data structures that act as containers for any data type you can think of.

Solution to this would be to use std::vector

std::vector<std::string> words;

---

Also this:

vector<string> *acc = new vector<string>();

• I don't recommend returning C++ containers, but if you happen to have a C++11 compatible compiler, then it avoids the copying overhead by simply moving the object...I digress

• Definitely try to avoid returning pointers to STL containers due to the fact that it could lead to memory leaks. Raw pointers are as a result of C but just because it's there doesn't mean you should use them. If you really must use pointers, use the ones provided by C++. C++ has a notion of smart pointers which are pointers that are aware of the object they point to, thus leading to automatically freed objects when the object does out of scope. Here is an article explaining smart pointers.

• If you must modify a value within a function or in an attempt to prevent having to pass-by-copy, I believe you should prefer pass-by-reference over passing the address of the value as a pointer. Pass by reference has a cleaner look to it (no need to dereference as in *ptr) and allows you to use the objects as if the current scope is the scope in which the object was defined (i.e. you can change the value of the object an the change will be evident after the function returns)

Functions

Functions are good as they help modularize your code so that you can separate independent functionalities in a useful manner. You have quite a few of them in your code, and that's good but...do you really need a function to check parameters? Imagine what happens when you call a function.

1. The parameters of the function and return address have to be pushed onto the stack frame for the function
2. Execution jumps to the memory address containing the function
3. The parameters are popped from the stack (plus other necessary cleanup)
4. The body of the function is now executed
5. Result stored somewhere
6. Stack freed
7. Execution resumes at the return address
8. Something else I might be missing

My point with this is that by calling a function to just check a few things, you are incurring quite a lot of overhead and could have saved some of your time by performing the check within the code that used that function. Also this is the only place where the function is used and it is relatively short.

Hint: Most of the time, programming contests give you input that is already within the constraints specified, so there is no need to explicitly recheck the input. Case and point, this problem you are solving already has the inputs checked against the constraints

Permutations

Is it too late to tell you that C++ also has a function for calculating the next lexicographically larger permutation of a given string? Yup! It's called std::next_permutation (surprise, surprise). It also runs in O(N) time in the length of the string, whereas the current one you have will run in exponential time as it has to compute all the permutations of the string.

Putting it all together

Here is what the code (untested) boils down to when it comes down to using pure C++ functionality. It is even possible to reduce it further to remove the vector and copy_n.

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>

int main() {
    int test_cases = 0;
    std::cin >> test_cases;
    std::vector<std::string> words;

    std::copy_n(std::istream_iterator<std::string>(std::cin),
                test_cases std::back_inserter(words));

    std::transform(words.begin(), words.end(),
                   std::ostream_iterator<std::string>(std::cout, "\n"),
                   [&](std::string &word) {
                       if (std::next_permutation(word.begin(), word.end())) {
                           return word;
                       }
                       return "no answer";
                   });
    return 0;
}

If you have questions about anything, just comment

Answer 2

Algorithm

As you've noted, your program becomes unusable when the input words get large. The challenge states that the words can be up to 100 letters long. There are 100! (~10^200) permutations in a 100 letter string. No computer on Earth has that kind of storage capacity. What you need to do is directly construct the next permutation.

Note two things:

• The largest permutation is when the letters are reverse-sorted (largest to smallest): 'dcba' for the letters 'a', 'b', 'c', and 'd'.
• The smallest permutation is when the letters are sorted: 'abcd' from above.

The algorithm for forming the next permutation goes like this:

1. If the letters of a word are already in reverse-sorted order, then that is the last permutation, so there's no answer.
2. Otherwise, find the smallest suffix of the word that is not reverse-sorted. This suffix will have the form of a single letter followed by one or more letters in reversed-sort order.
3. Switch the first letter of the suffix with the next-largest letter in the rest of the suffix. This results in a larger word.
4. Sort the suffix letters after the first in smallest-to-largest order. This results in the smallest word larger than the original.

Example: "skzmh"

1. "skzmh" is not in reversed-sort order, so there is a next largest.
2. The longest unsorted suffix:
   • "h" is reverse-sorted.
   • "mh" is reverse-sorted.
   • "zmh" is reverse-sorted.
   • "kzmh" is not reverse-sorted.
3. The next largest letter after 'k' in "zmh" is 'm'. Switch 'k' and 'm': "mzkh".
4. Sort the suffix after the first letter: "mhkz"

So, the next largest word after "skzmh" is "smhkz". Check that this is true.

Now that I've read @smac89's answer, I see there's a next_permutation() function built-in to C++. Oh well.

Your Code

This is the strangest mix of C and C++ code styles I've seen. Why are you using both std::string and char*? Why both std::vector and dynamically allocated arrays (new[])? None of your news are deleted, so you're leaking memory everywhere, meaning you couldn't handle large words even without the space and time issues. If you consistently use std::vector and std::string, the memory will be freed automatically when they go out of scope and are no longer needed.

Instead of string *words = new string[test_cases];, use vector<string> words. Then, you can do words.push_back(w); instead of keeping track of an index.

I'm assuming that permutations(string word) returns a vector<string>* pointer so it doesn't have to be copied when passing to find_lexicographically_bigger(). You can also pass by constant reference: const&: find_lexicographically_bigger(const string& words, const vector<string>& perms). The argument is const because it will not be modified, and the reference & means no copy will be made.

You can get rid of every new call in this code and it will run with less memory and will be easier to read.