So I've been wasting my time again researching suffix sorting algorithms, evaluating new ideas by hand and in code. But I always struggle to remember the type of my suffixes! Can you tell me which type my suffixes are?

Left-most what?

A lot of suffix sorting algorithms (SAIS, KA, my own daware) group suffixes into different types in order to sort them. There are two basic types: S-type and L-type suffixes. S-type suffixes are suffixes that are lexicographically less (Smaller) than the following suffix and L-type if it is lexicographically greater (Larger). A left-most S-type (LMS-type) is just that: A S-type suffix that is preceeded by a L-type suffix.

The special thing about these LMS-type suffixes is that once we sorted them we can sorted all the other suffixes in linear time ! Isn't that awesome?

The challenge

Given a string assume it is terminated by a special character that is less than any other character in that string (e.g. smaller than even the null byte). Output a type corrosponding char for each suffix.

You can freely choose which char to use for which type but I'd prefer L, S and * for L-, S- and LMS-type as long as they are all printable (0x20 - 0x7E).


Given the string mmiissiissiippi output (when using L, S and *):


For example the first L is due to the fact that mmiissiissiippi$ is lexicographically greater than miissiissiippi$ (the $ represents the added minimal character):

L - mmiissiissiippi$ > miissiissiippi$
L - miissiissiippi$  > iissiissiippi$
* - iissiissiippi$   < issiissiippi     and preceeded by L
S - issiissiippi$    < ssiissiippi$
L - ssiissiippi$     > siissiippi$
L - siissiippi$      > iissiippi$
* - iissiippi$       < issiippi$        and preceeded by L
S - issiippi$        < ssiippi$
L - ssiippi$         > siippi$
L - siippi$          > iippi$
* - iippi$           < ippi$            and preceeded by L
S - ippi$            < ppi$
L - ppi$             > pi$
L - pi$              > i$
L - i$               > $

Some more examples:

"hello world" -> "L*SSL*L*LLL"
"Hello World" -> "SSSSL*SSLLL"
"53Ab§%5qS"   -> "L*SSL*SLL"


I'm not here to annoy Peter Cordes (I'm so gonna do this on stackoverflow sometime); I'm just very lazy so this is of course ! The shortest answer in bytes wins.

Edit: The order of the chars is given by their byte value. That means compare should be like C's strcmp.

Edit2: Like stated in the comments output should be a single character for each input character. While I assumed that would be understood as "return a string" it seems at least 1 answer returns a list of single characters. In order to not invalidate the existing answers I will allow you to return a list of single characters (or integers which when printed result in only 1 char).

Tips for linear time:

  1. It can be done in 2 parallel forward iterations or in a single backward iteration.
  2. The state of each suffix depends only on the first 2 chars and the type of the second.
  3. Scanning the input in reverse direction you can determine L or S like this: $t=$c<=>$d?:$t (PHP 7), where $c is the current char $d the previous and $t the previous type.
  4. See my PHP answer. Tomorrow I will award the bounty.
  • \$\begingroup\$ This is my first question :) Sandbox got two upvotes and no comments so I think its ready to be posted. Feel free to make suggestions ! \$\endgroup\$
    – Christoph
    Jun 13, 2017 at 5:55
  • \$\begingroup\$ What characters can appear in the input? \$\endgroup\$ Jun 13, 2017 at 5:58
  • \$\begingroup\$ @MartinEnder all chars your string supports e.g. even the null byte for c++ style strings. Think of it as binary data. \$\endgroup\$
    – Christoph
    Jun 13, 2017 at 5:59
  • \$\begingroup\$ What does * mean? \$\endgroup\$
    – Leaky Nun
    Jun 13, 2017 at 6:03
  • \$\begingroup\$ @LeakyNun * means the corresponding suffix is of type left most s-type. A S-type suffix that is preceeded by a L-type suffix.. \$\endgroup\$
    – Christoph
    Jun 13, 2017 at 6:05

10 Answers 10


Haskell, 64 53 48 42 bytes


Try it online!

Ungolfed, with Char instead of Int:

suffixes :: String -> String
suffixes = go 'S'
   go :: Char -> String -> String
   go _ "" = ""
   go lorstar s | s > tail s = 'L' : go '*' (tail s)
                | otherwise  = lorstar : go 'S' (tail s)
  • \$\begingroup\$ Anonymous functions are allowed, so the z= can be removed. \$\endgroup\$ Jun 13, 2017 at 15:17
  • \$\begingroup\$ I just can't read Haskell. Would you mind giving me a brief explaination? \$\endgroup\$
    – Christoph
    Jun 13, 2017 at 17:04
  • 1
    \$\begingroup\$ @Christoph : the go function takes two arguments. The first is the character that represents what should be used to describe the S situation. The second is a string. It goes through that string recursively, removing the first character at each step (that's what tail does). The trick is that the first argument is set to * when the previous result was a L, or S otherwise. That way, in the case where an * or an S should be used, that first argument can be used directly. Hope that makes sense. \$\endgroup\$
    – bartavelle
    Jun 13, 2017 at 20:58
  • \$\begingroup\$ That's quite a nice idea ! I'm hoping to see more clever ideas :) \$\endgroup\$
    – Christoph
    Jun 13, 2017 at 21:04
  • \$\begingroup\$ @ØrjanJohansen how am I supposed to prepare the result in TIO? \$\endgroup\$
    – bartavelle
    Jun 13, 2017 at 21:36

Jelly,  25 23 21 20  19 bytes


A full program that prints the list of characters, using:

L: 0
S: 8
*: 9

(As a link it returns a list where all items are characters except the last one, which is a zero.)

Try it online! or see the test suite (with conversion to LS*).


Ṛ;\UỤỤIṠµI2n×ịØDṚ;0 - Link: list of characters, s  e.g. "cast"
Ṛ                   - reverse                           "tsac"
  \                 - cumulative reduce by:
 ;                  -   concatenation                   ["t","ts","tsa","tsac"]
   U                - upend (reverse each)              ["t","st","ast","cast"] (suffixes)
    Ụ               - sort indexes by value             [3,4,2,1] (lexicographical order)
     Ụ              - sort indexes by value             [4,3,1,2] (order of that)
      I             - incremental differences           [-1,-2,1] (change)
       Ṡ            - sign                              [-1,-1,1] (comparisons)
        µ           - monadic chain separation, call that x
         I          - incremental differences           [0,2] (only (-1,1) produce 2s)
          2         - literal 2                         2
           n        - not equal?                        [1,0] (indexes of * will be 0)
            ×       - multiply by x (vectorises)        [-1,0,1] (make indexes of *s 0)
              ØD    - decimal yield                     "0123456789"
             ị      - index into (1-indexed & modular)  ['8','9','0']
                Ṛ   - reverse                           ['0','9','8']
                 ;0 - concatenate a zero                ['0','9','8',0]
                    - implicit print                     0980
                    -                              i.e. "L*SL"
  • \$\begingroup\$ Would you mind adding a small explaination for me ? \$\endgroup\$
    – Christoph
    Jun 13, 2017 at 7:37
  • 2
    \$\begingroup\$ I will do of course - I am thinking about possible golfs first... \$\endgroup\$ Jun 13, 2017 at 7:37
  • \$\begingroup\$ 17 bytes \$\endgroup\$
    – Leaky Nun
    Jun 13, 2017 at 9:42
  • \$\begingroup\$ @LeakyNun How did you work that out?! You are using a bug there I think + on strings seems to vectorise but the underlying results are not actually Jelly iterables but strings (!) (e.g. try +@/L€ or +@/L€€ or ...) \$\endgroup\$ Jun 13, 2017 at 10:48
  • \$\begingroup\$ @JonathanAllan yes, + produces actual string. This is an undocumented feature, or what you call bug. \$\endgroup\$
    – Leaky Nun
    Jun 13, 2017 at 10:51

Python 3, 92 87 74 69 65 bytes

while s:d=s<s[1:];print(d+(c<d),end='');s=s[1:];c=d

Uses 0 for L, 1 for S, and 2 for *. Wrap the input string in quote characters; I believe this is allowed by convention.

Try it online!

Example use:


saved 5 bytes thanks to Leaky Nun, 4 bytes thanks to ovs


JavaScript (ES6), 51 45 bytes


Saved 6 bytes thanks to @Neil.

A recursive solution to the exercise.


console.log(f('mmiissiissiippi')); //LL*SLL*SLL*SLLL   002100210021000
console.log(f('hello world'));     //L*SSL*L*LLL       02110202000
console.log(f('Hello World'));     //SSSSL*SSLLL       11110211000
console.log(f('53Ab§%5qS'));       //L*SSL*SLL         021102100

  • \$\begingroup\$ Save 6 bytes: f=(c,d)=>c&&(d<(d=c<(c=c.slice(1))))+d+f(c,d) \$\endgroup\$
    – Neil
    Jun 13, 2017 at 18:38
  • \$\begingroup\$ Thanks, @Neil, I knew there had to be an optimization in there somewhere. \$\endgroup\$ Jun 13, 2017 at 18:53

JavaScript (ES6), 52 bytes

<input oninput=o.textContent=f(this.value)><pre id=o>

Port of @L3viathan's answer.

  • 1
    \$\begingroup\$ @RickHitchcock Oops, somehow I managed to port c=1 as c=0... \$\endgroup\$
    – Neil
    Jun 13, 2017 at 18:35

C (clang), 88 bytes


Try it online!


Haskell, 77 75 bytes, linear time

f(a:b:c)|let g"L"|a<b="SL";g"S"|a>b="L*";g d=d++d;d:e=f$b:c=g[d]++e
f _="L"

Try it online!

How it works

This uses recursion, stripping off one character at a time from the beginning of the string. (The Haskell string type is a singly-linked list of characters, so each of these steps is constant-time.)

  • For a string abc where a and b are single characters and c is any (possibly empty) string,
    • f(abc) = SLe, if f(bc) = Le and a < b;
    • f(abc) = L*e, if f(bc) = Se and a > b;
    • f(abc) = LLe, if f(bc) = Le and ab;
    • f(abc) = SSe, if f(bc) = Se and ab.
  • For a single-character string a, f(a) = L.
  • 1
    \$\begingroup\$ Could you please provide an explanation? \$\endgroup\$
    – R. Kap
    Jun 19, 2017 at 20:32
  • \$\begingroup\$ Please provide a description so I can validate that this runs in linear time. \$\endgroup\$
    – Christoph
    Jun 22, 2017 at 5:51
  • \$\begingroup\$ @Christoph Added. \$\endgroup\$ Jun 22, 2017 at 6:54
  • \$\begingroup\$ @AndersKaseorg thanks for adding ! Sadly this seems quite verbose compared to the other Haskell answer. Could this be golfed further by not using S, L and *? \$\endgroup\$
    – Christoph
    Jun 22, 2017 at 7:16
  • 1
    \$\begingroup\$ @Christoph To be clear, [1,1,2,0,1,1,2,0,1,1,2,0,1,1,1] is a list of single-digit numbers, not a list of single chars. In my case, I think outputting a list of numbers would not save me any bytes. \$\endgroup\$ Jun 22, 2017 at 9:19

Python 2, 65 55 bytes

Recursive version, based on L3viathan's answer, using 012 as LS*:

def g(s,d=2):c=s<s[1:];return s and`c+(d<c)`+g(s[1:],c)

Try it online!

Python 3, 65 59 bytes

Recursive solution using L, S, and *:

f=lambda s:s and('LS'[s<s[1:]]+f(s[1:])).replace('LS','L*')

Runs through the string from the front, and replaces all instances of LSwith L*

Try it online!

  • 1
    \$\begingroup\$ blah if s else''s and blah saves six bytes. In Python 2, str(blah)`blah` saves another three bytes on the second solution. \$\endgroup\$ Jun 22, 2017 at 9:58

PHP, 82 byte, linear time

for($a=$argn;a&$c=$a[$i-=1];$d=$c)$a[$i]=2+$t=$d<=>$c?:$t;echo strtr($a,[13=>12]);

Walks over the input from right to left and replaces each char with the type.


Calculates the type given the current and the previous char (-1 or 1). If equal the type doesn't change.

  • \$\begingroup\$ +1 for the idea with strtr \$\endgroup\$ Jun 24, 2017 at 12:58

PHP, 70 bytes

L = 1, S = 0 , * = 2

Multibyte Support is needed for the last Testcase with the § +3 Bytes mb_substr instead substr


Try it online!

PHP, 71 bytes

L = 1, S = 0 , * = 2

for(;$s=&$argn;$s=$u)$r.=+($s>$u=substr($s,1));echo strtr($r,[10=>12]);

Try it online!

PHP, 74 bytes

for(;$s=&$argn;$s=$u)$r.=SL[$s>$u=substr($s,1)];echo strtr($r,[LS=>"L*"]);

Try it online!

  • \$\begingroup\$ $s=&$argn quite clever ! I'm pretty sure there is a better answer though ;) Hopefully someone comes up with it :) \$\endgroup\$
    – Christoph
    Jun 13, 2017 at 16:56
  • \$\begingroup\$ @Christoph I have the feeling that I am miss something. I have try to store the last LS* in a varibale but it is longer \$\endgroup\$ Jun 13, 2017 at 17:01
  • \$\begingroup\$ @Christoph mean you like so? I coul not really seen why the last testcase is false Try it online! \$\endgroup\$ Jun 13, 2017 at 20:08
  • \$\begingroup\$ @Christoph Okay I have seen it why it not works for the last testcase I must use mb_substr instead of substr if the input is not in the simple ascii range. Is it necessary to support the last testcase? \$\endgroup\$ Jun 13, 2017 at 20:51
  • 1
    \$\begingroup\$ @Christoph Thank You In this case I ignore the last testcase with the § \$\endgroup\$ Jun 13, 2017 at 21:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.