O(n)/O(1) time/space using van Emde Boas Tree
The van Emde Boas (vEB) tree can find successor and predecessors of a given letter in O(log log u) time and O(u) space where u is the number of possible letters
The van Emde Boas (vEB) tree can find successor and predecessors of a given letter in O(log log u) time and O(u) space where u is the number of possible letters in the alphabet; 26 in this case. Using vEB is a sledge hammer to the thumbtack of a problem here; but its kinda fun to learn vEB\'s using a toy problem. I have seen several O(n)/O(1) solutions in the discussion I recommend anyone of those over this solution unless you want some vEB exposure. \n\nThis youtube video covers the subject well https://www.youtube.com/watch?v=hmReJCupbNU&t=4178s.\n\nThe following solution implements a basic binary vEB with O(log u) time to find its predecessor/successor and O(u) space. \n\n```\npublic string SortString(string s) {\n\t// keeps track of the binary vEB tree\n\t// each bit indicates whether or not its corresponding cluster has an item\n\tvar tree = 0ul; \n\tvar freq = new int[26];\n\tfor (int i = 0; i < s.Length; ++i) add(s[i] - \'a\');\n\n\tvar res = s.ToArray();\n\tvar (j, x) = (0, default(int?));\n\twhile (tree > 0) {\n\t\twhile ((x = nxt(x ?? -1)).HasValue) {\n\t\t\tres[j++] = (char)(x.Value + \'a\');\n\t\t\trmv(x.Value);\n\t\t}\n\t\twhile ((x = prv(x ?? 32)).HasValue) {\n\t\t\tres[j++] = (char)(x.Value + \'a\');\n\t\t\trmv(x.Value);\n\t\t}\n\t}\n\treturn new string(res);\n\n    // adds a new value to the frequency list and vEB tree\n\tvoid add(int i)\n\t{\n\t\tif (freq[i]++ == 0) // add i to the vEB if its the first time we are adding i\n\t\t{\n\t\t\ti += 31; // translate to the value to the appropriate leaf index in the vEB\n\t\t\t// walk up the anscestors path setting them to 1 to indicate the new value exists\n\t\t\twhile ((tree & 1ul << i) == 0)\n\t\t\t{\n\t\t\t\ttree |= 1ul << i; // set the bit at i to 1\n\t\t\t\ti = (i - 1) / 2; // move to the parent\n\t\t\t}\n\t\t}\n\t}\n\n    // removes a value from the frequency list and vEB tree\n\tvoid rmv(int i)\n\t{\n\t\tif (--freq[i] == 0) // remove i from the vEB if we just removed the last instance from freq \n\t\t{\n\t\t\ti += 31; // translate to the value to the appropriate leaf index in the vEB\n\t\t\t// walk up the anscestors path setting them to 0 if they have no children\n\t\t\tdo\n\t\t\t{\n\t\t\t\ttree ^= 1ul << i; // set the bit at i to 0\n\t\t\t\ti = (i - 1) / 2; // move to the parent\n\t\t\t} while (tree > 0 && ((tree & 1ul << 2 * i + 1) | (tree & 1ul << 2 * i + 2)) == 0); // neither child has a value\n\t\t}\n\t}\n\n    // finds the next value in the vEB after i and returns null if not found\n\tint? nxt(int i)\n\t{\n\t\tif (tree == 0 || i > 30) return null; // the tree is empty or there can\'t be a larger item\n\t\ti = i < 0 ? 31 : i + 32; // translate the value to the first vEB leaf index that could be the successor\n\t\tvar m = 63; // one more than the largest value in the lowest layer\n\t\twhile (i < m) // while there can still potentially be a successor value\n\t\t{\n\t\t\t// check if the successor value is in the current cluster\n\t\t\tif ((tree & 1ul << i) > 0) break;\n\t\t\tif (i % 2 == 1 && (tree & 1ul << ++i) > 0) break;\n\t\t\t\n\t\t\t// we didn\'t find it in this cluster, lets move to the cluster just after the current clusters parent\n\t\t\ti = (i - 1) / 2 + 1;\n\t\t\tm = (m - 1) / 2;\n\t\t}\n\t\tif (i >= m) return null; // we found the successor does not exist\n\t\t// we know the current cluster\'s descendants contain the successor, lets drill down to the left most descendant  \n\t\twhile (i < 31)\n\t\t\ti = (tree & 1ul << 2 * i + 1) > 0 ? 2 * i + 1 : 2 * i + 2;\n\t\treturn i - 31;\n\t}\n\n\t// finds the previous value in the vEB before i and returns null if not found\n\tint? prv(int i)\n\t{\n\t\tif (tree == 0 || i < 1) return null; // the tree is empty or there can\'t be a smaller item\n\t\ti = i > 31 ? 62 : i + 30; // translate the value to the first vEB leaf index that could be the predecessor\n\t\tvar m = 30; // one less than the minimum value in the lowest level \n\t\twhile (i > m) // while there can still potentially be a previous value\n\t\t{\n\t\t\t// check if the previous value is in the current cluster\n\t\t\tif ((tree & 1ul << i) > 0) break; \n\t\t\tif (i % 2 == 0 && (tree & 1ul << --i) > 0) break; \n\t\t\t\n\t\t\t// we didn\'t find it in this cluster, lets move to the previous parent cluster\n\t\t\ti = (i - 1) / 2 - 1;\n\t\t\tm = (m - 1) / 2;\n\t\t}\n\t\tif (i <= m) return null; // we found a predecessor does not exist\n\t\t\n\t\t// we know a previous exits somewhere under the children of this cluster\n\t\t// we drill down to the right most leaf from the current cluster\n\t\twhile (i < 31)\n\t\t\ti = (tree & 1ul << 2 * i + 2) > 0 ? 2 * i + 2 : 2 * i + 1;\n\t\treturn i - 31; // translate the leaf index back to the value \n\t}\n}\n```
[]