Longest Stringly-Furthering Substring

Code Golf

string counting optimization add tag

Mathgeek

String parsing this time!


## Task

Input is a string of indeterminate length, composed of any number of upper or lowercase letters.

Your goal is to find the longest strictly-furthering substring. This means making sure the next letter comes later than in the alphabet than the previous.

For the purpose of this challenge, all capital letters are strictly greater than all lowercase letters. [a-z][A-Z] is our order, first-to-last, smallest-to-largest.

a can only ever be our first letter, and Z could only ever be our last.

The output should print the longest strictly-increasing substring. In the event there are more than one that ties, print out either.

Input is the entry string, output is the output substring, I/O is fairly tight.

## Sample Test Cases

| Input | Output|
| :-: | :-: |
| ajrleowple | ajr OR eow |
|flwpeAREP | flw OR eAR |
|epejikwEIOepoaWlpd | ikwEIO |
| [blank string] | [blank string] |
|[alphabet in lowercase followed by uppercase] | [Same as input]|
|zyxwvutsrqponm| [Any one of those letters] |
|f|f|
|qqqqqqqrrrrrrr| qr|

Python 3 95 bytes

Anonymous 1951

Python 3 ~~174~~ ~~146~~ ~~104~~ 98 bytes

wizzwizz4

[Jelly](https://github.com/DennisMitchell/jelly), 9 bytes

xigoi

Top Answer Python 3

Anonymous 1951

# 95 bytes

	f=lambda s:list(s.swapcase())!=sorted(set(s.swapcase()))and max(f(s[1:]),f(s[:-1]),key=len)or s

Similar logic as the answer provided by wizzwizz4, but using `sorted(set(s.swapcase()))` and `list(s.swapcase())` instead of `sorted(set(s),key=lambda c:ord(c)^32)` and `list(s)`. This saves one byte. Also using a version of
    
    condition and this or that

instead of

	this if condition else that

This saves two more bytes.

Answer #2 Python 3

wizzwizz4

# ~~174~~ ~~146~~ ~~104~~ 98 bytes
    f=lambda s:s if sorted(set(s),key=lambda c:ord(c)^32)==list(s)else max(f(s[1:]),f(s[:-1]),key=len)

[Try it online!][TIO-kgp19ub8]

This is a functional solution.

## Explanation

    f=lambda s:...

A `lambda` is an anonymous function. This will be assigned to the variable `f`.

    s if ... else max(f(s[1:]),f(s[:-1]),key=len)

Returns `s` (the input) if it's a strictly-furthering string; otherwise, returns the longest of "`f` called with the beginning chopped off `s`" and "`f` called with the end chopped off `s`". Given that `s` _isn't_ a strictly-furthering string, the longest strictly-furthering substring of `s` must be missing (at least) either the first or last character of `s` – so try both, and get the longest (the `max`imum, if you're `key`ing off the strings' `len`gths).

Another way of thinking of this is that all substrings can be reached by repeatedly chopping off either the beginning or the end of the string. (In fact, there are many ways to reach most substrings… but who cares about efficiency? This is code golf!) This, then, explores the tree of all such substrings, terminating at strictly-furthering substrings and then taking the maximum of each branch when it climbs back up the tree. (What do you mean, trees don't grow down?)

All single-character strings are strictly-furthering strings, as is the empty string, so this will always terminate. Eventually.

    sorted(set(s),key=...)==list(s)

A strictly-furthering string doesn't contain duplicates; `set` removes those. `sorted` produces a `list` of the duplicate-free substring sorted by the order function. This is equal to `list(s)` iff (if and only if) `s` is strictly-furthering.

    lambda c:ord(c)^32

Python strings use the Unicode character encoding. Because it's based on ASCII, the Latin alphabet is encoded like this:

|UPPER| `76543210` | |lower| `76543210` |
|  -: | :-         |-|  -: | :-         |
| `A` | `01000001` | | `a` | `01100001` |
| `B` | `01000010` | | `b` | `01100010` |
| `C` | `01000011` | | `c` | `01100011` |
| `D` | `01000100` | | `d` | `01100100` |
| ... |            | | ... |            |
| `W` | `01010111` | | `w` | `01110111` |
| `X` | `01011000` | | `x` | `01111000` |
| `Y` | `01011001` | | `y` | `01111001` |
| `Z` | `01011010` | | `z` | `01111010` |

Currently, the upper-case alphabet sorts lower than (i.e. before) the lower-case alphabet – but by flipping bit `5` of the numerical representation (i.e. XORing `ord(c)` with `32`) this can be reversed, giving the correct sorting order. (Effectively, this is toggling the case of the letters.) Since numbers sort the same as letters, there's no need to convert it back with `chr`.

This would completely trash the rest of the Unicode characters, but fortunately the ASCII letters are the only characters in the input.

[TIO-kgp19ub8]: https://tio.run/##RY1LU4MwFIX3@RVZkhlc1O6YYVGVan1Ra7U@ps4EuEhKIOEmFOifR2h1/Fbn3HvOHN3ZTJXTvk99yYso4dR4hoqUGoUWEseAdQxzc@j@/rGnMHFi9jU9Z74vhRkDIA3QgrdO6pjPibdl7ii8s8n2twsl65tMSKBrrMEjdMBidxIjhvpUlLq2DjveoI1BWxqE8wBR4X8wQuD50WkU5TDu0mGLsZ7vUIJqtASSykbDbBUsCWjYibwJFiFoxTdSJ4TwKE4g/c7ELpdFqXSFxtb7pu0Os4vLq2B@fbO4vbt/eAyXT6vn9cvr5u39gxy6ttnX1mClVVmQlFQn8MQP "Python 3 – Try It Online"

Answer #3

xigoi

# [Jelly], 9 bytes

    ẆŒsÞ⁼QƊƇṪ

[Try it online!][TIO-khokysvg]

[Jelly]: https://github.com/DennisMitchell/jelly
[TIO-khokysvg]: https://tio.run/##AS8A0P9qZWxsef//4bqGxZJzw57igbxRxorGh@G5qv///2VwZWppa3dFSU9lcG9hV2xwZA "Jelly – Try It Online"

## Explanation

    ẆŒsÞ⁼QƊƇṪ   Main monadic link
    Ẇ           Sublists
           Ƈ    Filter by
          Ɗ     (
       Þ          Sort by
     Œs             Swap case
        ⁼         Equals?
         Q        Unique
          Ɗ     )
            Ṫ   Last element

3 Answers