# Backronymiser឵឵

## Background

A backronym is an acronym that was formed from an existing word. For example, spam is actually named after the canned meat product as used in the Monty Python sketch, but can be interpreted as "stupid pointless annoying mail".

## Challenge

Given a string a, and a word t, capitalise the correct letters of the words in a such that they spell out t. You should always move left-to-right through a, and capitalise the first occurrence of each letter.

For example, if a is all the worlds a stage, and t is LAG, then we walk along the letters of all the worlds a stage:

• we look for the first l and capitalise it: aLl the worlds a stage
• now we look for the next a, but it must be after the previously found l: aLl the worlds A stage
• now we look for a g: aLl the worlds A staGe.

You may assume a will only contain lowercase ASCII letters and spaces.

You may assume t will only contain ASCII letters. You should choose whether t will be input in uppercase or lowercase.

You do not need to handle empty inputs or inputs that have no possible backronymisation.

## Test cases

a                            t        output
================================================================
never gonna give you up      VIP      neVer gonna gIve you uP
all the worlds a stage       LAG      aLl the worlds A staGe
why                          WHY      WHY
baacbbccba                   ABC      bAacBbCcba
x                            X        X
xxxx                         X        Xxxx
yellow submarine time        YEET     YEllow submarinE Time


## Rules

• Related Jul 11 at 6:55
• Also related, possibly Jul 11 at 7:03
• also related
– att
Jul 11 at 7:08
• Suggested testcase: "vyxal is terse elegant and readable", "YEET" (double letters) Jul 11 at 7:13
• This challenge's name has haunted me since the first time I saw it. I think the onymiser substring and syllable count put it just close enough to my username to simulate the uncanny valley effect. Jul 14 at 13:11

# C (gcc), 49 bytes

f(char*a,char*t){for(;*a;)*a++^=*a-*t?0:32+!++t;}


Try it online!

Modifies a in place. Input t lowercase.

# Python 3.10, 7673475751 49 bytes

def f(a,t,i=0):
for c in t:a[i:=a.find(c,i)]-=32


Attempt This Online

Takes in a and t as byte arrays with UTF-8 encodings with t lowercase, modifies a in place.

-3 bytes from @pxeger for replacing the double spaces with single spaces (I blame my IDE for auto-converting my tabs)
-26 bytes from @Cong Chen because the rules allow you to take in a list of characters and modify it in place (I should have read the rules more carefully)
+10 bytes from @Cong Chen because all of the previous methods just didn't work properly (not sure how to notate this)
-6 bytes by using code points instead of characters
-2 bytes from @loopy walt by using byte arrays & walrus operator

# Prolog (SWI), 55 bytes

[H|T]+Z+[X|P]:-[H|B]=Z,X is H-32,T+B+P;X=H,(T+Z+P;P=T).


Try it online!

-33 bytes thanks to Jo King

Recursive.

x#[]=x
(h:t)#a@(x:b)|h==x=h-32:t#b|1>0=h:t#a


Try it online!

I/O as codepoints. -2 bytes thanks to alephalpha

• (h:t)#(x:b)...#(x:b) -> (h:t)#a@(x:b)...#a Jul 12 at 1:44
• one more byte
– Jo King
Jul 14 at 5:33

# Vyxal, 12 bytes

v=vTΠ~Þ⇧h⁽⇧V


Try it Online! I/O as char lists.

I feel like there's gotta be a smarter/faster way to do Π~Þ⇧h.

v=           # Create an equality table
vT         # Get all indices of each letter in the string
Π        # Take the cartesian product, getting all combinations
~Þ⇧     # Filter by those which are strictly ascending
h    # Get the first, which will be the first occurences
V # To those indices in the original string...
⁽⇧  # Uppercase them

• @Steffan Clever, but that's completely different. You can post it :P Jul 11 at 21:23

# Curry (KICS2) + :set +first, 61 bytes

import Data.Char
(f s)#(g s)=s
f=map toLower
g=filter isUpper


Finds a string s such that converting s to lowercase gives a, and picking out the uppercase characters in s gives t.

Curry is a functional logic programming language. It searches for solutions using backtracking. Without :set +first it would return all possible solutions. With :set +first it only gives the first one.

This works on KICS2 3.0.0. It seems that it does not work on PAKCS or older versions of KICS2.

• Looks nice, can you add a short explainer? Jul 11 at 9:56

# x86-64 machine code, 11 bytes

AC AE 75 FD 80 67 FF DF 75 F6 C3


Try it online!

Following the standard calling convention for Unix-like systems (from the System V AMD64 ABI), this takes the addresses of a and t, as null-terminated byte strings, in RDI and RSI, respectively, with t lowercase, and modifies a in place.

In assembly:

f:  lodsb       # Load a character from t into AL, advancing the pointer.
rc: scasb       # Compare AL with a character from a, advancing the pointer.
jne rc      # Jump back to repeat if they are not equal.
and BYTE PTR [rdi-1], 0xDF  # Set bit 5 of the matching character to 0, capitalizing it.
jnz f       # Jump to the start if the result is not 0.
ret         # Return (once the null terminator is reached).


# J, 49 bytes

toupper@[(0{"1[:(|.~"#:0,2>:/\{."1)^:_[:I.=/)]}


Try it online!

This challenge resisted all my attempts to find a short array paradigm solution.

I tried more than 5 approaches, and my best result is still rather long.

It's interesting to contrast how simple it is to solve procedurally -- you need only a single loop and a single register.

## my best idea

The interesting part of the solution is calculating the indices of the uppercase letters.

Consider 'abc' f 'xbacbcb'.

• First we construct an equality table:

0 0 1 0 0 0 0
0 1 0 0 1 0 1
0 0 0 1 0 1 0

• And then convert each row to the indices of its ones, with zero fill:

2 0 0
1 4 6
3 5 0

• Finally, we start rotating any "out of order" rows to the left. A row is out of order if first element is not greater than the first element of the row above. We continue rotating until a fixed point is reached: the entire first column is increasing.

Focus on first column
|
v
2 0 0
1 4 6  <-- 1 less than 2, so rotate
3 5 0

2 0 0
4 6 1
3 5 0  <-- 3 less than 4, so rotate

2 0 0
4 6 1
5 0 3  <-- now 2, 4, 5 increasing, so done

• We now have our answer: 2 4 5 are the indices we need to capitalize.

# Retina, 27 bytes

i+(.)(.+)/(\1)
$3¶$2/
¶|/



Takes input separated by /.

Try it online!

# Java (JDK), 40 bytes

a->t->a.map(c->t.peek()!=c?c:t.pop()^32)


Try it online!

With a is an Stream<Integer> (stream of codepoints) and t is a Deque<Integer>. Both inputs are lowercase.

There's a lot going on with automatic null tests, autoboxing and friends, so this answer might seem trivial, but it's actually not at all.

# K (ngn/k), 24 bytes

-1 byte from @ngn's improvement

{c$x-32*y{y_x,y~:*x}/x}  Try it online! Adapted from my answer on the Speed of Lobsters code golf. • y{...}/x set up a reduction seeded with y (the characters to search for), run over the characters in x (the full string). confusingly, within the function itself, x and y are flipped. this ends up returning a boolean array with 1s in the positions containing the desired matches and 0s everywhere else • y~:*x compare the first character to search for (*x) to the current character being iterated over (y), updating y with the result of 0 or 1. note that as soon as we have matched all the search characters, no more matches will be identified (since a character will never ~ (match) a 0 or 1) • x, append this result to the list of characters to search for (essentially overloading the reduction to end up returning the desired output) • y_ if there was a match, drop the first character (if there wasn't a match, this is a no-op). this allows us to search for the next search character in the next iteration of the reduction • c$x-32* multiply this bitmask by 32, representing the offset necessary to capitalize characters at truthy indices, subtract it from the original text, and convert that result "back" to a string/text
• x+-32* -> x-32*
– ngn
Jul 13 at 17:40

# JavaScript (Node.js), 62 bytes

f=(a,[h,...l])=>a.replace(eval(/${h}(.*)/i),(s,t)=>h+f(t,l))  Try it online! Input uppercase t. # R, 55 54 bytes \(s,t)sapply(s,\(c){if(F<-t[1]%in%c)t<<-t[-1];c-32*F}) Attempt This Online! Input is vector of codepoints. # R, 61 bytes \(s,t)for(c in s){if(t[1]%in%c){c=toupper(c);t=t[-1]};cat(c)} Attempt This Online! Function with null return value that prints output to console. Input is vector of characters. # Vyxal, 9 bytes £ƛ¥h=[&Ḣ⇧  Try it Online! Literally is different by one character from this, and also very similar to this. Input as strings, output as char list. (s flag in link smashes) £ƛ¥h=[&Ḣ⇧ £ # Put the first input in the register ƛ # Map over the second input: ¥h=[ # Is the current character equal to the first character of the register? &Ḣ⇧ # If so, remove the first character of the register and uppercase the current character # (implicit) else, return the current character unchanged  # Brachylog (v2), 10 bytes ↔{|ụ}ᵐ↔w₆⊇  Try it online! Function submission, using both its arguments (input string on the left, uppercase acronym on the right) and outputting to standard output. Very inefficient (O(2n) performance). ## Explanation ↔{|ụ}ᵐ↔w₆⊇ ᵐ Iterate over {the left argument} ↔ ↔ in reverse order {| either doing nothing (try this option first) |ụ} or uppercasing {the character being iterated over} ⊇ such that {the right argument} is a subsequence of {the result} w₆ and when we find it, output {the result of the iteration}  Uppercase some of the characters so that we can find the acronym in the uppercased string. The inefficiency comes from the fact that the iteration order will try uppercasing the first character, then the second, then the first two, then the third, then the first and third, then the second and third, then the first three, then the fourth, etc. – the interpreter doesn't realise that the first solution it finds will uppercase a number of characters exactly equal to the length of the right-hand argument (because any solution which uppercases too many characters will be found later, and any solution that doesn't uppercase enough won't match), so it just tries all possibilities within a given prefix before going onto the next character. Iterating in reverse is required for the uppercasing of prefixes to be the first thing the interpreter requires (with the normal iteration method, it would try uppercasing the last character first, etc.). w₆ (which outputs the current value, without discarding it, and where the output is used only if all the constraints in the rest of the program end up matching) is by far the most useful of Brachylog's nine write instructions, so could probably do with a 1-byte representation (I would likely make this the default behaviour for a write if I were designing a Brachylog-alike from scratch). # Perl 5-plF , 36 35 bytes saved a byte by taking the first input in upper case $_=<>;s/./uc$&eq$F[0]?shift@F:$&/ge  Try it online! Takes t on the first input line in upper case, then a on the second line. # Rust, 149 148 bytes |m:&str,v:&str|{m.chars().fold(v.chars().peekable(),|mut a,c|{print!("{}",if a.peek()==Some(&((c as u8+32)as char)){a.next().unwrap()}else{c});a});} Attempt This Online! # 05AB1E, 11 bytes v¬yQićuëy}?  Inputs as lowercase strings in the order $$\a,t\$$. Explanation: v # Loop over the characters y of the first (implicit) input-string a ¬ # Push the first character of string t # (which will be the implicit second input-string t in the first iteration) yQi # If it's equal to character y: ć # Extract the first character from string t u # And uppercase it ë # Else: y # Push character y as is } # After the if-else statement: ? # Pop this character, and print it  # Pyth, 15 bytes ?Lqrd4h+Q0.(Q0E  Accepts t then a on separate lines as lists of characters and returns a list of characters. # Factor, 55 bytes [ [ over index cut capitalize swap write ] each print ]  Try it online! Takes the string and the lowercase word in that order. Assuming the input is "all the worlds a stage" "lag" • [ ... ] each For each letter in the word...  <<iteration 1 of each>> ! "all the worlds a stage" 108 over ! "all the worlds a stage" 108 "all the worlds a stage" index ! "all the worlds a stage" 1 cut ! "a" "ll the worlds a stage" capitalize ! "a" "Ll the worlds a stage" swap ! "Ll the worlds a stage" "a" write ! "Ll the worlds a stage" (write to stdout without newline) <<iteration 2 of each>> ! "Ll the worlds a stage" 97 over ! "Ll the worlds a stage" 97 "Ll the worlds a stage" index ! "Ll the worlds a stage" 14 cut ! "Ll the worlds " "a stage" capitalize ! "Ll the worlds " "A stage" swap ! "A stage" "Ll the worlds " write ! "A stage" (write to stdout without a newline) <<and so forth..>> ! "Ge" print ! (write to stdout with a newline)  • Mind adding a short explanation? Jul 12 at 7:16 • @Jonah Completed. Jul 12 at 9:31 # K (ngn/k), 36 bytes Takes the string as first argument, then the acronym in lowercase. {@[x;(#x)-1+#'x{y/1_y\x}\y;c$-;32]}


Try it online!

# Go, 70 bytes

func s(a,b[]byte){i:=0;for _,c:=range b{for a[i]-32!=c{i++};a[i]-=32}}


Try it online!

# Jelly, 16 bytes

ẹⱮŒpI>0PƊƇḢ
Œuç¦


Try it online!

ẹⱮŒpI>0PƊƇḢ - Helper link g(s, w) - takes string on the left and word on the right.
ẹⱮ          -  For each character in w, get all indices of it in s.
Œp        -  Take the cartesian product over this list.
Ƈ  -  Filter keep for:
I       -   Increments (deltas / consecutive differences)
>0     -   Are they greater than zero? (positive)
P    -   Take the product of is to check that all are truthy
Ḣ -  Get the first item (that satisfies that condition)

Œuç¦   - Main link f(s, w) - takes string on the left and word on the right.
ç    - Run the helper link (as a dyad, given s and w)
¦   - At those indices in w...
Œu     - Uppercase them

• Procedural Jelly?! Funky Jul 15 at 6:28

# Charcoal, 22 bytes

Ｆη«≔⌕θ↧ιζ…θζι≔Φθ›λζθ»θ


Try it online! Link is to verbose version of code. Explanation:

Ｆη«


Loop over the uppercase letters.

≔⌕θ↧ιζ


Find the index of the next matching lowercase letter.

…θζ


Output its prefix.

ι


Output the uppercase letter.

≔Φθ›λζθ


Remove the prefix and the lowercase letter from the string.

»θ


Output any remaining lowercase letters.

• This is cutting off all letters following the last capitalized letter. Example Aug 8 at 7:27
• @Deadcode Whoops, over-optimised for the selected test case...
– Neil
Aug 8 at 8:34

# PHP, 90 bytes

function($a,$t,$i=0){foreach(str_split($a)as$c)echo($z=$c^' ')==@$t[$i]?[$z,++$i][0]:$c;};


Simply loops through the characters in the string, and outputs the capitalized one when necessary.

This is an anonymous function, so, it has to be given to a variable to be called.

You can try it on here: https://onlinephp.io/c/61a1c
(Contains all test cases in the question.)

## How it works?

It uses the fact that XORing an ASCII character with a space, will toggle the 3rd bit, which will change the letter case.
With this knowledge, I avoid running strtoupper($c), saving me a bunch of bytes. This is useful for checking against the backronym letters, which are in upper case, and to display the upper case letter. These are accomplished in ($z=$c^' ')==@$t[$i]. The @ is there to suppress warnings, which will happen when we exhaust all characters in $t.

To make the code shorter, I've used [$z,++$i][0], which displays the upper case character and increments $i, without the need to make an if. The (much longer) alternative is the following: if(($z=$c^' ')==@$t[$i]){++$i;echo$z;}else echo$c;


One edge-case that people may see as an issue, is with spaces.
However, if you XOR a space with a space, it gives a null character (\0).
Luckily, a null character is a truthy value.

Another possible edge-case, with spaces, comes from the fact that, after the $t string is exhausted, the value will be null. Since the null character is a truthy value, and null is a falsy value, this will never be true, which means that I can use == instead of ===, and saves 1 byte. # Lua, 71 bytes a,b=...;j=1;for i=1,#a do x=a[i]-32;if x==b[j]then a[i]=x j=j+1 end end  Try it online! Chunk which modifies a in place. Mostly equivalent to the Go solution. # knight, 68 60 bytes ;;=aP=bP;=j=i 0W<iLa;O I-32-A=cGa i 1A=dGb j 1c;=j+1j d=i+1i  Try it online! -8 bytes thanks to Adam for some nice spacing rearrangements In my J answer, which required a lot of machinery, I noted: It's interesting to contrast how simple it is to solve procedurally -- you need only a single loop and a single register. Since knight is a very simple procedural language, I thought it would make an interesting juxtaposition. ## how ;=j=i 0 # initialize indices for the two input strings ; ;=aP=bP # read the inputs into variables a and b W<iLa # while (i < a.length)... ;O I-32-A=cGa i 1A=dGb j 1 # Take the ascii difference between the chars # a[i] (store it in c) and b[i] (store in d), # and subtract that from 32 c # if the difference is not 0, return c (the lowercase) ;=j+1j d # if it is 0, return d (the uppercase) and # increment j =i+1i # increment i in either case  • Some minor spacing changes get it down to 61 bytes: ;=j=i 0;;=aP=bP W<iLa;O I-32-A=cGa i 1A=dGb j 1c;=j+1j d=i+1i – Adam Aug 6 at 21:28 • Also, if you want to print all of the characters on one line, you can append a slash to the end of each output call: ;;=aP=bP;=j=i 0W<iLa;O+I-32-A=cGa i 1A=dGb j 1c;=j+1j d"\"=i+1i – Adam Aug 6 at 21:40 • You also also swap the first two assignments to remove a byte: ;;=aP=bP;=j=i 0W<iLa;O I-32-A=cGa i 1A=dGb j 1c;=j+1j d=i+1i – Adam Aug 6 at 23:39 # Retina 0.8.2, 45 bytes +r^((?i:\3))(.*)([a-z])([^A-Z]*)$
$2$1$4 ^  Try it online! Link includes test cases. Takes the word and string separated by spaces. Explanation: +r^((?i:\3))(.*)([a-z])([^A-Z]*)$
$2$1$4  Repeatedly match the earliest lowercase letter in the string which doesn't precede an uppercase letter that case insensitively matches the first letter of the word and move that (uppercase) letter into its place. The match is performed in right-to-left order as this makes the test simpler. ^  Remove the space that separated the word and the string. # C# (Visual C# Compiler), 103 bytes (a,t)=>{for(int i=-1,j=-1;++i<t.Length;)for(;;)if(a[++j]==t[i]){a[j]=(char)(t[i]-32);break;}return a;};  Try it online! • It's been a while and this is the "dumb" approach so I'm sure there are improvements that can be made, Jul 20 at 9:36 • Suggest int i=0,j=-1;for(;i<t.Length;a[j]=(char)(t[i++]-32))for(;a[++j]!=t[i];); instead of for(int i=-1,j=-1;++i<t.Length;)for(;;)if(a[++j]==t[i]){a[j]=(char)(t[i]-32);break;} Jul 30 at 15:24 # Regex (.NET), 69 bytes s/.(?=(.*$)(?<=(?=(?>.*?(.)(?=.*
((?>\3?)(\2))))+\1$)^.*))| .*/$4/img


Try it online! - all test cases
Try it on regex101! - try it on your own

This is a single regex substitution, to be applied once. This is the only kind of substitution that can be efficiently used on regex101.

Input is taken in the form of the two strings delimited by a newline.

The primary challenge here is that each match+substitution must be done as a separate event, with no communication between them (other than that each subsequent match is done following the end of the previous one). No captures can survive from one match to the next, so each one must reconstruct its state from scratch, relying only on the position of the match to let it do that.

Also note that the actual replacement is only done after all matches are found, so that can't be used to communicate state.

In this explanation, a raw newline is shown as ¶:

s/                                     # Match the following:
.                                # Match a character in string A
(?=                              # Lookahead (keep this out of what will
# be replaced)
(.*$) # \1 = capture the rest of string A, to # our position (?<= # Lookbehind - evaluated from right to # left, so read from the bottom up (?= # Lookahead - go back to evaluating from # left to right. (?> # Atomic group - after each iteration, # lock in its match and prevent # backtracking. .*? # Skip as few characters as possible, # minimum zero, to match the following: (.) # \2 = a character in string A (?= # Lookahead .*¶ # Skip to the beginning of string T ( # \3 = concatenation of the following: (?>\3?) # Previous value of \3, if set (\2) #$4 = the next character in string T
#      (which is capitalized)
)
)
)+                   # Loop the above as many times as
# possible, minimum one, to make the
# following match:
\1$# Stop at the point we snapshotted, # making sure that the string ends after # it, to prevent matching an earlier # duplicate. ) ^.* # First step in the lookbehind - skip # back to the beginning of the string. ) ) | # or... ¶.* # Match the newline and string T, in # order to erase it. / # Substitution - replace with this:$4                                     # The capital letter we captured in $4, # which will be empty if it was the # second alternative that matched. / # Flags: i # Case Insensitive (so that letters in # string T will match those captured in # string A) m # Multiline - "$" matches the end of any
# line instead of just the end of string.
g                                      # Global - replace all matches instead of
# only the first.


# Regex (Pythonregex), 74 bytes

s/.(?=(.*$)(?<=(?=(?>.*?(.)(?=.* (?=(\4?))(\3+(\2))))+\1$)^.*))|
.*/\5/img


Try it online!

Since mrab-regex supports variable-length lookbehind, the only adaptation necessary in this port was to eliminate the use of nested backreferences. Groups \4 and \5 are copied between each other.

The old version of mrab-regex on TIO has a bug (seemingly similar to an old bug in PCRE1) which necessitated changing (...)+\1$ to (...)+?\1$ making the regex 75 bytes, but this is fixed in the latest version (which is not on TIO and not yet on ATO).

# Regex (Perl / PCRE), 86 bytes

s/.(?=(.*)
(.)+((?<=(?=^(?>.*?(.)(?=.*
(\5?+(\4))))+\1
.*(?=\2)\4|(?3)).)))|
.*/$2/sig  Try it online! - Perl - all test cases Try it online! - PCRE1 - all test cases Try it online! - PCRE2 v10.33 / Attempt This Online! - PCRE2 v10.40+ - all test cases Try it on regex101! - PCRE1/PCRE2 - try it on your own This is a port of the .NET regex, emulating variable-length lookbehind using recursion with fixed-length lookbehind, but there's an additional challenge. The .NET regex makes a capture inside the lookbehind which is used as the substitution replacement. That is impossible in Perl/PCRE, since all captures made inside a subroutine (recursive or not) are erased upon exiting it. So to communicate back from the emulated lookbehind, this regex makes a guess (\3, captured by (.)+) as to what the capital letter in string t will be, and then compares that with the capital letter actually matched inside the lookbehind ((?=\3)\5). If it's not a match, the regex will backtrack to before the emulated lookbehind, and try capturing a different capital letter from string t. # Regex (GNU ERE or better), 30 bytes s/(.)(.*( ))(\1)| /$4$3$3$2/ig  Try it online! - ECMAScript Try it online! - Perl Try it online! - PCRE1 Try it online! - PCRE2 Try it online! - Boost Try it online! - Python Try it online! - Python import regex Try it online! - Ruby Try it online! - .NET This is a single regex substitution to be repeatedly applied until it has nothing to match (or until there is no change, in engines whose API doesn't supply the information as to whether anything was matched – i.e. ECMAScript, Boost, and Python). Input is taken as string a and word t concatenated with a newline delimiter between them. This is similar to Leaky Nun's 27 byte Retina solution, but that one does two regex substitutions (looping the first until there is no change, then applying the second one once, then done) and uses two different types of delimiters at once (newline and slash), while this solution does just one looping regex substitution, and only uses newlines as a delimiter. The intermediate states as this one progresses are different than those in the 27 byte Retina solution. In it, as the first stage progresses, it inserts a newline after each capitalized letter in string a and deletes the corresponding letter from the beginning of word t. It's only in its second stage that the newlines in string a are deleted. As this 30 byte regex substitution progresses, it inserts two newlines after each capitalized letter in string a and deletes the corresponding letter from the beginning of word t – but as it progresses, the previous double newline gets deleted; at any given step (other than before it starts), only the letter last changed to uppercase has two newlines after it. Then when no letters are left to capitalize, it deletes all the newlines. s/ # Match the following: (.) # \1 =$1 = one character from string A (which is in lowercase)
(         # $2 = concatenation of the following: .* # Match as many non-newline characters as possible, minimum zero (¶) #$3 = one newline
)
(\1)      # $4 = the first character in word T (which is in uppercase) | # or ¶ # One newline / # Replace with the following:$4            # The uppercase letter from word T, replacing $1$3$3 # Two newlines inserted$2            # $2, preserved unchanged from string A # No$4 – it is deleted from the beginning of word T
# Note that all of the above will be empty if the second
# alternative, one newline, was what matched, thus deleting
# the newline.
/             # Flags:
i             # Case Insensitive
g             # Global - replace all matches instead of only the first. After
# after the end of the last full match (i.e. they don't overlap).
# The replacement pass is only done after all matches are found.


# Ruby, 52 bytes

->s{0while s.gsub! /(.)(.*(
))(\1)|
/i,'\4\3\3\2';s}


Try it online!

# Retina, 28 bytes

i+(.)(.*(¶))(\1)|¶
$4$3$3$2


Try it online!

# Perl -p0, 37 bytes

1while s/(.)(.*(
))(\1)|
/$4$3$3$2/ig


Try it online!

# GNU sed-z, 39 bytes

:a
s/(.)(.*(\n))(\1)|\n/\4\3\3\2/Mig
ta


Try it online!

The M flag tells . to match everything except newline, whereas normally in sed, .` matches any character including newline.