| Bytes | Lang | Time | Link |
|---|---|---|---|
| 162 | Python | 241216T052308Z | tsh |
| 056 | K ngn/k | 250103T175145Z | coltim |
| 143 | Python | 241218T024911Z | Albert.L |
| 472 | Java | 241216T151048Z | Abhay Tr |
| 070 | K ngn/k | 241220T021726Z | att |
| 174 | Python 3 | 241214T203807Z | Uri Gran |
| 302 | Wolfram Language Mathematica | 241216T144057Z | Introduc |
| 221 | Maple | 241218T174859Z | dharr |
| 017 | Jelly | 241216T001958Z | Jonathan |
| 162 | Retina | 241214T220239Z | Neil |
| 023 | 05AB1E | 241217T083135Z | Kevin Cr |
| 269 | Google Sheets | 241215T072334Z | doubleun |
| 030 | Japt v2.0a0 h | 241216T110120Z | Shaggy |
| 049 | Charcoal | 241215T082232Z | Neil |
| 128 | JavaScript ES6 | 241215T002804Z | Arnauld |
| 110 | Perl 5 ap | 241215T055008Z | Xcali |
Python, 162 bytes
lambda s:min((g:=lambda p,a,b:a and g(p+f' {a}'[t:=a[0]==b[:1]],a[1:],b[t:])or[b,-len(w),p])('',re.sub(fr'\b{w}\b',w.upper(),s),w)for w in s.split())[2];import re
-5 bytes by Jonathan Allan -2 bytes by STerliakov
K (ngn/k), 56 bytes
{r@*<+/'1+^r:w@'<'>'w{y_x,y~:*x}/'x/'+(,'w)@'=#w:x\y}" "
Hat-tip @tubular for trimming a bunch off.
Another adaptation of my Speed of Lobsters golf, with pieces lifted from @att's answer.
{...x/'+(,'w)@'=#w:x\y}" "fixxas" "and generate strings, each replacing a single word with spaces (this is taken directly from @att's answer)r:w@'<'>'w{y_x,y~:*x}/'do the Speed of Lobsters thing, storing results inrr@*<+/'1+^ridentify the result that contains the longest valid word (and return it)
Python, 143 bytes
lambda s:max([(j:=0)or''.join(w[j:(j:=j+(z==w[j:j+(v!=w)]))]or' 'for v in s.split()for z in v+' ')[:0-j//len(w)]for w in s.split()],key=sorted)
Still feels like there is some slack left.
History:
Python, 147 bytes
lambda s:max([(j:=0)or''.join(' '*(z!=w[j:j+1]or v==w)or z[:(j:=j+1)]for v in s.split()for z in v+' ')[:-(w[:j]==w)]for w in s.split()],key=sorted)
This one avoids the super-expensive substring replacement. Turns out that is worth jumping through a hoop or two.
Python, 151 bytes
lambda s:max([''.join(D[c==w[j:j+1]and(j:=j+1)]for c in f' {s} '.replace(D,D.upper()))[1:-(w[j:]<D)]for w in s.split()if[j:=0,D:=f' {w} ']],key=sorted)
Python, 152 bytes
lambda s:max([''.join(D[c==[*w,0][j]and(j:=j+1)]for c in f' {s} '.replace(D,D.upper()))[1:-(w[j:]<D)]for w in s.split()if[j:=0,D:=f' {w} ']],key=sorted)
Python, 153 bytes
lambda s:max([''.join(D[c==[*w,0][j]and(j:=j+1)]for c in f' {s} '.replace(D,len(D)*' '))[1:-(w[j:]<D)]for w in s.split()if[j:=0,D:=f' {w} ']],key=sorted)
Python, 160 bytes
lambda s:max([''.join(c*(c==D[j-1:j]!=[j:=j+1])or' 'for c in f' {s} ~'.replace(D,len(D)*' '))[1:j//len(D)*-2]for w in s.split()if[j:=1,D:=' %s '%w]],key=sorted)
Java , 472 bytes
> edit : addition of lastIndexmatcher so it ensures wd in orderr.
import java.util.Scanner;
class Subsequenc {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
// Input the string and the word
System.out.print("Enter the string: ");
String str = sc.nextLine();
System.out.print("Enter the word: ");
String wd = sc.nextLine();
// Result array initialized with spaces
char ch[] = new char[str.length()];
for (int i = 0; i < ch.length; i++) {
ch[i] = ' ';
}
// Track the position of the last matched character
int lastMatchedIndex = -1;
// Match logic
for (int i = 0; i < wd.length(); i++) {
char currentChar = wd.charAt(i);
boolean found = false;
for (int j = lastMatchedIndex + 1; j < str.length(); j++) {
if (str.charAt(j) == currentChar) {
ch[j] = currentChar; // Add the matched character
lastMatchedIndex = j; // Update the last matched index
found = true;
break; // Move to the next character in wd
}
}
if (!found) {
// If a character in wd isn't found after lastMatchedIndex, stop processing
break;
}
}
// Print the result
for (char c : ch) {
System.out.print(c);
}
}
}
K (ngn/k), 70 bytes
{*<c!+/'^c:a{(,'y)@'(#*|b)|x~':b:x{(*x=y)_x}\y}'x/'+(,'a)@'=#a:x\y}" "
Wonder if there's a non-brute-force better way.
a:x\y words
x/'+(,'a)@'=# each whited out in input
a{ }' subsequences:
(,'y)@' x~':b:x{(*x=y)_x}\y fill in a subsequence
(#*|b)| only if all chars present
*<c!+/'^c: min by #spaces
Python 3, 186 174 bytes
A quick not-very-golfed solution; I expect it's possible to do much better. Might try again if I get some time. (PS Thanks @tsh for saving 11 bytes, and @jonathan-allan for saving 1 more.)
import re
def f(s):
for w in sorted(s.split(),key=len)[::-1]:
t=re.sub(fr"\b{w}\b",w.upper(),s);o=""
for c in w:n=t.find(c);o+=" "*n+c;t=t[n+1or len(t):]
if~n:return o
Wolfram Language (Mathematica), 302 bytes
f[i_]:=(s=StringSplit[i];c=First@MaximalBy[Cases[s,Alternatives@@LongestCommonSequence@@@Transpose@{StringRiffle@Delete[s,#]&/@Range@Length@s,s}],StringLength];j=1;StringJoin@@Select[Map[If[#==(Characters@c)[[j]],j+=1;#," "]&,Characters@StringRiffle@(s/.c->StringRepeat[" ",StringLength[c]])],StringQ])
Maple, 221 bytes
proc(s)uses StringTools;b:=" ";for u in sort(Words(s),length)do L:=length(u);t:=Substitute(cat(s,b),cat(u,b),cat(b$L+1));j:=1;c:=cat([for i in t do if i=u[j] then j++;i else b fi od][]);`if`(j-1=L,(g:=c[..-2]),x)od;g end;
proc(s) uses StringTools; # input string s
b:=" ";
for u in sort(Words(s),length) do # sort words in increasing length
# so last and longest success is returned
L:=length(u);
t:=Substitute(cat(s,b),cat(u,b),cat(b$L+1)); # replace word with spaces;
# pad word and s with space so doesn't
# substitute within a longer word
j:=1;
c:=cat([for i in t do if i=u[j] then j++;i else b fi od][]); # scan with i
# pointing in string and j in word
`if`(j-1=L,(g:=c[..-2]),x) # success recorded in g if word was
# finished (strip previously added space)
od;
g # return g
end;
Jelly, 30 29 28 21 19 17 bytes
-7 porting Kevin Cruijssen's approach in their 05AB1E answer (as proposed in the "Could probably be..." note above my original answer, below). Also -4 more golfing this.
JŒPṬoḲix@ʋƇo¬ao⁶
A monadic Link that accepts a list of characters and yields a list of characters.
Try it online! (although it's too slow for the longer test cases).
How?
JŒPṬoḲix@ʋƇo¬Ṫao⁶ - Link: Plaintext
J - indices of {Plaintext} -> AllIndices
ŒP - powerset of {AllIndices} (shortest to longest)
Ṭ - untruth -> AllMasks (each with ones at the chosen indices and
zeros elsewhere up to the last chosen index)
Ƈ - keep those of {AllMasks} for which:
ʋ - last four links as a dyad - f(Mask, Plaintext):
o - {Mask} logical OR {Plaintext} (vectorises)
-> Masked (Plaintext with ones in place of chosen indices)
Ḳ - split {Masked} at space characters -> WordsOfMasked
x@ - {Plaintext} repeat {Mask} (vectorises)
-> Substring (i.e. the characters at the chosen indices)
i - first 1-indexed index of {Substring} in {WordsOfMasked}
...or 0 if not found
-> ValidMasks (ordered from fewest to most set bits)
¬ - {Plaintext} logical NOT -> Zeros = [0,0,...,0] (Plaintext's length)
o - {ValidMasks} logical OR {Zeros} (vectorises)
(right pads each mask with zeros to the length of Plaintext)
Ṫ - tail -> ValidMaskWithMaximalSetBits
a - {ValidMaskWithMaximalSetBits} logical AND {Plaintext} (vectorises)
-> X = Plaintext with zeros where we want spaces
o⁶ - {X} logical OR with a space character (vectorises)
(replaces the zeros with spaces)
Original, 28 bytes
-1 inspired by Niel's comment about the original having two helper Links :)
Could probably be slightly terser by using a more bute-force approach (think partitions or powersets) - EDIT: yep, see above.
⁶µḲ¬i¦KẹⱮŒpʋⱮ`ẎQṢ$ƑƇLÞṪḟ@Jµ¦
A monadic Link that accepts a list of characters and yields a list of characters.
How?
⁶µ...µ¦ - Link: Plaintext e.g: "a word is missing mate"
¦ - sparse application to {Plaintext}...
µ µ - ...to indices: monadic chain - f(Plaintext) -> SpaceIndices
⁶ - ...apply: space character -> " i s "
Ḳ¬i¦KẹⱮŒpʋⱮ` - start of the monadic chain: Plaintext
Ḳ - split {Plaintext} at space characters -> PlaintextAsWords
Ɱ` - map across TrialWord in {PlaintextAsWords} with:
ʋ - last four links as a dyad - f(PlaintextAsWords, TrialWord}
e.g. f(["a","word","is","missing","mate"], "is")
¦ - sparse application to {PlaintextAsWords}...
i - ...at indices: first index of {TrialWord} in {PlaintextAsWords}
¬ - ...apply: logical NOT (vectorises)
K - join with space characters -> RedactedPlaintext, e.g:
['a',' ','w','o','r','d',' ',0,0,' ','m','i','s','s','i','n','g',' ','m','a','t','e']
Ɱ - map across Character in {TrialWord} with:
ẹ - indices of {Character} in {RedactedPlaintext}
[[12,15],[13,14]]
Œp - Caterisan product -> AllIndexPicksMakingTrialWord
[[12,13],[12,14],[15,13],[15,14]]
-> AllIndexPicksMakingTrialWordForEachWord
[[[20]],[],[[12,13],[12,14],[15,13],[15,14]],[],[]]
ẎQṢ$ƑƇLÞṪḟ@J - the rest of the monadic chain: AllIndexPicksMakingTrialWordForEachWord
Ẏ - tighten
[[20],[12,13],[12,14],[15,13],[15,14]]
Ƈ - keep those for which:
Ƒ - is invariant under?:
$ - last two links as a monad:
Q - deduplicate
Ṣ - sort
[[20],[12,13],[12,14]
LÞ - sort by length (to place the longest ones on the right)
Ṫ - tail -> KeepCharactersAt
[12,14]
J - indices {Plaintext} -> AllIndices
ḟ@ - {AllIndices} filter discard {KeepCharactersAt}
-> SpaceIndices
[1,2,3,4,5,6,7,8,9,10,11,13,15,16,17,18,19,20,21,22]
Retina, 189 180 162 bytes
L$`\b((\w)+)\b(?=(.)*(?<=(?(2)$)((?<-2>\2)|.)*\1(?<-3>(?<-2>\2)|.)*))
$& $`$.&* $'
N^$`
$.&
0G`
|""L$`\G(?<=(.)*)(\w)(?=\w* ((?<-1>\1)|.)*?(?(1)$)(.*?)\2)
$.4* $2
Try it online! Link includes test cases. Explanation:
L$`\b((\w)+)\b(?=(.)*(?<=(?(2)$)((?<-2>\2)|.)*\1(?<-3>(?<-2>\2)|.)*))
$& $`$.&* $'
Find all of the words that are subsequences of the remaining string. .NET balancing groups are used twice, firstly ?<-2> matches the subsequence and secondly ?<-3> ensures that the original word is skipped at the right place when matching the subsequence. (Note that the lookbehind is processed right-to-left, so that the (?(2)$) is actually the last part of the regex.) For each word, prefix it to the input with that word replaced with spaces.
N^$`
$.&
0G`
Sort in reverse order of length and keep only the longest word.
|""L$`\G(?<=(.)*)(\w)(?=\w* ((?<-1>\1)|.)*?(?(1)$)(.*?)\2)
$.4* $2
Find the subsequence and output only those letters with the appropriate amount of spacing.
05AB1E, 24 23 bytes
ā<DæéR.ΔÎrǝð¡IyèJå}Kðsǝ
-1 byte fixing a bug found by @JonathanAllan (yes, -1 byte, not +1 😅)
(Don't) try it online.
To speed it up slightly, so it can at least output some test cases: try it online or verify multiple smaller test cases at once.
Explanation:
ā< # Push a list in the range [0, (implicit) input-length)
D # Duplicate this indices-list
æ # Pop and get the powerset of the copy
éR # Sort the from longest to shortest
.Δ # Pop and find the first that's truthy for:
Î # Push 0 and the input-string
r # Reverse the stack order
ǝ # Insert the 0 at the current indices into the input
ð¡ # Then split on spaces
I # Push the input-string again
yè # Get the characters at the current indices
J # Join this list of characters to a string
å # Check if it's in the list
}K # After the find_first: remove those indices from the full indices-list
ðsǝ # Insert spaces at all remaining indices in the (implicit) input
# (after which the result is output implicitly)
The (slightly) faster version has éR replaced with I#€gêù€`R:
I # Push the input-string
# # Split it on spaces
€g # Get the length of each word
ê # Uniquify and sort those lengths (smallest to largest)
ù # Only keep the powerset-lists of those lengths
€` # Flatten the list one level down
R # Reverse the list, so the order is from longest to shortest
Google Sheets, 269 bytes 313 bytes
=let(b,"(.*)",w,tocol(split(A1," ")),sort(reduce(,sort(w,len(w),0),lambda(a,t,let(l,len(t),s,substitute(A1,t,rept(" ",l),1),p,b&join(b,mid(t,sequence(l),1))&b,o,join("_",regexextract(s,p)),i,sequence(len(o)),if(a=0,ifna(join(,if(mid(o,i,1)="_",mid(s,i,1)," "))),a))))))
Put the phrase in cell A1 and the formula in B1.
The formula uses simple regexes only and doesn't rely on lookaround or backtracking. Bonus: works for outruled repetitions like one to one and example example as well.
Ungolfed:
=let(
words, tocol(split(A1, " ")),
sorted, sort(words, len(words), 0),
sort(reduce(, sorted, lambda(a, t, let(
length, len(t),
stripped, substitute(A1, t, rept(" ", length), 1),
letters, mid(t, sequence(length), 1),
pattern, "(.*)" & join("(.*)", letters) & "(.*)",
opposite, join("_", regexextract(stripped, pattern)),
i, sequence(len(opposite)),
if(a = 0,
ifna(join(, if(mid(opposite, i, 1) = "_", mid(stripped, i, 1), " "))),
a
)
))))
)
Japt v2.0a0 -h, 45 39 35 31 30 bytes
¸£¸hYXç)¸Ë¶XÎ?X=ÅD:SÃpÂ!XÃñè\a
¸£¸hYXç)¸Ë¶XÎ?X=ÅD:SÃpÂ!XÃñè\a :Implicit input of string U
¸ :Split on spaces
£ :Map each X at index Y
¸ : Split U on spaces
hY : Replace the element at index Y with
Xç : Fill X with spaces
) : End replace
¸ : Join with spaces
Ë : Map each D
¶ : Is equal to
XÎ : First character of X
? : If true
X= : Reassign to X
Å : Remove first character from X
D : Return D
: : Else return
S : Space
à : End inner map
p : Repeat
 : Bitwise NOT of bitwise NOT of
!X : Logical NOT of X
à :End outer map
ñ :Sort by
è : Count of
\a : RegEx /[a-z]/g
:Implicit output of last element
Charcoal, 59 49 bytes
Ｆ⪪θ «≔⪪⮌ι¹ηＰ×⭆⪫Ｅ⪪θ ⎇⁼ικ⭆κ κ ⎇∧η⁼κ§η±¹⊟ηψ∧¬η›ＬιＬＫＡ
Try it online! Link is to verbose version of code. Explanation:
Ｆ⪪θ «
Split the input into words and loop over each word.
≔⪪⮌ι¹η
Start with all letters remaining to be matched. (The letters are reversed so that they can be easily removed as they are matched.)
Ｐ×⭆⪫Ｅ⪪θ ⎇⁼ικ⭆κ κ ⎇∧η⁼κ§η±¹⊟ηψ∧¬η›ＬιＬＫＡ
Replace the word in the original string with spaces, then replace all of the characters with nulls (which print as spaces but don't count as being printed, so the length of the previous result can be counted as the number of printed characters) except the letters from the word which are kept as they are matched. If this matched all of the letters, and this word is longer than any previously output word, then output the result, overwriting any previous result.
JavaScript (ES6), 128 bytes
-3 thanks to @l4m2
s=>s[R="replace"](/\w+/g,n=w=>w[q=s[R](RegExp(`\\b${w}\\b`),w[R](e=/./g,i=0))[R](e,c=>c==w[i]?++i&&c:" "),i]||n>i||(n=i,b=q))&&b
Commented
s => // s = input string
s[R = "replace"]( // replace in s
/\w+/g, // look for words
n = // n = best length so far, initially NaN'ish
w => // for each word w in s:
w[ // test w[i]:
q = // q is the string obtained by
s[R]( // replacing in s:
RegExp( // the (only) occurrence of w
`\\b${w}\\b` // surrounded by word boundaries
), //
w[R]( // with w where ...
e = /./g, // each character
i = 0 // is replaced with '0'
) // end of replace()
) // end of replace()
[R]( // replace again:
e, // each ...
c => // ... character c with:
c == w[i] ? // if c is w[i]:
++i && c // c itself (and increment i)
: // else:
" " // a space
), // end of replace()
i // i is the actual index for our test
] || // do nothing if w[i] is defined
// (i.e. the subsequence is incomplete)
n > i || // or n is greater than i
// (i.e. the best word b is longer)
(n = i, b = q) // otherwise, set n to i and b to q
) && b // end of replace(); return b
Perl 5 -ap, 110 bytes
$"=".*";map{@;=/./g;$m=$_,@l=@;if"@F"=~s/\b$_\b//r=~@;&@;>@l}@F;s/\b$m\b/' 'x@l/e;s/./$&eq$l[0]?shift@l:' '/ge