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|
Top Answer Python 3
# ~~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"
# [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