Solution Notes (Jonathan Paulson): A string appears earliest if its letters are sorted in alphabetical order (i.e. all 'a' before all 'b' before all 'c' ... before all 'z') and every other string was sorted in reverse alphabetical order. This is because taking any other string and creating a lexicographically larger one would only move it further back in the overall ordering. Similarly, a string appears latest if it's letters are sorted in reverse alphabetical order and every other string is sorted in alphabetical order.

This observation leads to a simple solution idea: make a list of all the strings in alphabetical and reverse alphabetical order, and sort them. Then run through the list, keeping track of how many alphabetical and reverse-alphabetical strings you've seen so far. When you run across a string in reverse alphabetical order, its latest possible position is the number of alphabetical strings you've seen so far minus 1 (for the alphabetical version of itself, which always comes before it, but shouldn't count). When you run across a string is alphabetical order, its earliest possible position is the number of reverse-alphabetical strings you've seen so far (no minus 1, because the reverse-alphabetical version of itself always comes later).

One detail: for this idea to work for strings whose two versions are the same (like "a" or "bb") you need to sort so that alphabetical versions come before reverse-alphabetical versions in case of a tie, or track whether the reverse version has already been encountered. Here is Travis Hance's solution in C++:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
using namespace std;

#define NMAX 50000
#define LENMAX 20

string cows[NMAX];

struct Entry {
    string st;
    int index;
    bool is_rev;
    bool operator<(Entry const& o) const {
        if (st == o.st) {
            return (!is_rev) && o.is_rev;
        }
        return st < o.st;
    }
};
Entry entries[NMAX*2];

int lowest[NMAX];
int highest[NMAX];

void compute(int n) {
    for (int i = 0; i < n; i++) {
        sort(cows[i].begin(), cows[i].end());

        entries[2*i].st = cows[i];
        entries[2*i].index = i;
        entries[2*i].is_rev = false;

        entries[2*i+1].st = cows[i];
        reverse(entries[2*i+1].st.begin(), entries[2*i+1].st.end());
        entries[2*i+1].index = i;
        entries[2*i+1].is_rev = true;
    }

    sort(entries, entries + (2*n));

    int rev_count = 0;
    for (int i = 0; i < 2*n; i++) {
        if (entries[i].is_rev) {
            rev_count++;
        } else {
            int index = entries[i].index;
            lowest[index] = rev_count + 1;
        }
    }

    int fwd_count = 0;
    for (int i = 2*n-1; i >= 0; i--) {
        if (!entries[i].is_rev) {
            fwd_count++;
        } else {
            int index = entries[i].index;
            highest[index] = n - fwd_count;
        }
    }
}

int main() {
    freopen("scramble.in","r",stdin);
    freopen("scramble.out","w",stdout);
    
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        cin >> cows[i];
    }

    compute(n);

    for (int i = 0; i < n; i++) {
        printf("%d %d\n", lowest[i], highest[i]);
    }
}

import java.util.*;
import java.io.*;
import java.awt.Point;
import static java.lang.Math.*;

public class scramble {
    public static void main(String[] args) throws Exception {
        Scanner in = new Scanner(new File("scramble.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new
FileWriter("scramble.out")));
        int n = in.nextInt();
        String[] BEST = new String[n];
        String[] WORST = new String[n];
        String[] IN = new String[n];
        for(int i=0; i<n; i++) {
            IN[i] = in.next();
            char[] str = IN[i].toCharArray();
            Arrays.sort(str);
            BEST[i] = new String(str);
            WORST[i] = new StringBuilder(new String(str)).reverse().toString();
        }
        Arrays.sort(BEST);
        Arrays.sort(WORST);
        for(int i=0; i<n; i++) {
            char[] S = IN[i].toCharArray();
            Arrays.sort(S);
            String bi = new String(S);
            String wi = new StringBuilder(bi).reverse().toString();

            int lo = Arrays.binarySearch(WORST, bi);
            if(lo < 0) lo = -(lo+1);
            lo++;

            int hi = Arrays.binarySearch(BEST, wi);
            if(hi < 0) hi = -(hi+1);
            else hi++;

            out.println(lo+" "+hi);
        }
        out.flush();
    }
}