UVa 1209 - Wordfish

// UVa 1209 - Wordfish

#include <string>
#include <iostream>
#include <algorithm>
#include <climits>
#include <map>
using namespace std;

map<char, int> idx;

int abs_dif(const string & st) {
	int dif = INT_MAX;
	for (int j = 1; j < st.length(); j++)
		dif = min(dif,
				(st[j] > st[j - 1] ? st[j] - st[j - 1] : st[j - 1] - st[j]));
	return dif;
}

int main() {
	string front;
	while (cin >> front) {
		string back = front, sol = front;
		int largest_abs_dif = abs_dif(front);
		bool hasNext = true, hasPrev = true;
		for (int i = 0; i < 10; i++) {
			if (hasNext) {
				hasNext = next_permutation(front.begin(), front.end());
				if (hasNext) {
					int front_abs_dif = abs_dif(front);
					if (front_abs_dif > largest_abs_dif) {
						largest_abs_dif = front_abs_dif;
						sol = front;
					}
				}
			}
			if (hasPrev) {
				hasPrev = prev_permutation(back.begin(), back.end());
				if (hasPrev) {
					int back_abs_dif = abs_dif(back);
					if (back_abs_dif >= largest_abs_dif) {
						largest_abs_dif = back_abs_dif;
						sol = back;
					}
				}
			}
		}
		cout << sol << largest_abs_dif << endl;
	}
	return 0;
}