Fix the spaces
Statement
Goal
You are given two strings, the first contains the original sentence, with words in the right order but no spaces. The second has the words in random order but with spaces to differentiate them. Fix the original sentence by adding spaces where they should be.Every test has at least one solution, but there are some cases where the original sentence can not unambiguously be deciphered. In those cases print
NB: Tests 1-14 cover simple cases and should help you debug your program. Tests 15-16 check the performance.
Input
Line 1 : A string. The original sentence, with words in the right order but no spaces.
Line 2 : A string containing the words in random order but with spaces to differentiate them.
Line 2 : A string containing the words in random order but with spaces to differentiate them.
Output
The original sentence with the necessary spaces added to it or the string Unsolvable .
Constraints
The original string only contains uppercase letters.
The words string only contains uppercase letters and spaces.
Each word in words appears the same number of times in words and in original.
Each string is at most1000 characters long.
The number of words is at most200 .
The words string only contains uppercase letters and spaces.
Each word in words appears the same number of times in words and in original.
Each string is at most
The number of words is at most
Example
Input
ABCDEFGHIJ DEF J ABC GHI
Output
ABC DEF GHI J
Tags
Backtracking, String manipulation
Difficulty
Medium
Test cases
1 Starters Test
Input
ABCDEFGHIJ
DEF J ABC GHI
Output
ABC DEF GHI J
1 Starters val Validator
Input
CODINGAME
ING COD AM E
Output
COD ING AM E
2 Prefix letter Test
Input
ABCAFEAHI
AHI AFE ABC
Output
ABC AFE AHI
2 Prefix letter val Validator
Input
CODCINGCAME
COD CING CAME
Output
COD CING CAME
3 Suffix letter Test
Input
ABCDFCGHC
ABC GHC DFC
Output
ABC DFC GHC
3 Suffix letter val Validator
Input
CODINGDGAMED
INGD COD GAMED
Output
COD INGD GAMED
4 Prefix words Test
Input
ABCDEABABCABCD
ABCD AB ABC ABCDE
Output
ABCDE AB ABC ABCD
4 Prefix words val Validator
Input
CODINGAMECODINGCCOD
CODING CODINGAME COD C
Output
CODINGAME CODING C COD
5 Suffix words Test
Input
ABCDBCDCD
CD ABCD BCD
Output
ABCD BCD CD
5 Suffix words val Validator
Input
CODINGINGDING
DING ING CODING
Output
CODING ING DING
6 Repeated Test
Input
ABCEDFEDFABC
EDF EDF ABC ABC
Output
ABC EDF EDF ABC
6 Repeated val Validator
Input
GHIBOBOBO
BO GHI BO BO
Output
GHI BO BO BO
7 Combo Test
Input
ABABCDCDEABCDEABCD
CDE AB ABCD CDE AB ABCD
Output
AB ABCD CDE AB CDE ABCD
7 Combo val Validator
Input
CODINGCODINCOCODINDING
CODIN CO DING DING CO CODIN
Output
CO DING CODIN CO CODIN DING
8 Unsolvable Test
Input
STARSTARSTAR
STARS TAR STAR
Output
Unsolvable
8 Unsolvable val Validator
Input
ABCEABCE
AB ABCE CE
Output
Unsolvable
9 Actually solvable Test
Input
SAPIENSAPIENPURUSPURUS
PURUS SAPIEN SAPIENPURUS
Output
SAPIEN SAPIENPURUS PURUS
9 Actually solvable val Validator
Input
ABABCECE
ABCE AB CE
Output
AB ABCE CE
10 Actually solvable 2 Test
Input
ABCABABC
AB ABC CAB
Output
AB CAB ABC
10 Actually solvable 2 val Validator
Input
DEDDE
D DE ED
Output
D ED DE
11 Actually solvable 3 Test
Input
AABABA
AB A ABA
Output
A AB ABA
11 Actually solvable 3 val Validator
Input
CCFFCFFC
C CFF CFFC
Output
C CFF CFFC
12 Actually solvable 4 Test
Input
ABABABA
BA AB ABA
Output
AB ABA BA
12 Actually solvable 4 val Validator
Input
AACAACAACAA
CAA AAC AACAA
Output
AAC AACAA CAA
13 Actually solvable 5 Test
Input
ABABABA
ABA ABA B
Output
ABA B ABA
13 Actually solvable 5 val Validator
Input
MOMOMOM
MOM O MOM
Output
MOM O MOM
14 Actually solvable 6 (Count well) Test
Input
AABABAA
AA B A B AA
Output
AA B A B AA
14 Actually solvable 6 (Count well) val Validator
Input
ABAABAABA
A B AA B AA B A
Output
A B AA B AA B A
15 Performance 1 (70 words) Test
Input
LOREMIPSUMDOLORSITAMETCONSECTETURADIPISCINGELITSEDDOEIUSMODTEMPORINCIDIDUNTUTLABOREETDOLOREMAGNAALIQUAUTENIMADMINIMVENIAMQUISNOSTRUDEXERCITATIONULLAMCOLABORISNISIUTALIQUIPEXEACOMMODOCONSEQUATDUISAUTEIRUREDOLORINREPREHENDERITINVOLUPTATEVELITESSECILLUMDOLOREEUFUGIATNULLAPARIATUREXCEPTEURSINTOCCAECATCUPIDATATNONPROIDENTSUNTINCULPAQUIOFFICIADESERUNTMOLLITANIMIDESTLABORUM
QUI IN CILLUM AUTE ULLAMCO ESSE INCIDIDUNT EA LABORUM ET NULLA ELIT MINIM IN EIUSMOD ALIQUA DESERUNT QUIS VOLUPTATE MOLLIT DOLOR OFFICIA UT ANIM DOLORE TEMPOR EU UT LABORIS SIT UT VENIAM PARIATUR SUNT CUPIDATAT CONSEQUAT CONSECTETUR OCCAECAT ENIM CULPA IPSUM AMET EXCEPTEUR EXERCITATION ADIPISCING COMMODO LOREM FUGIAT MAGNA NON VELIT AD PROIDENT LABORE DOLOR EST NOSTRUD DUIS SED IRURE NISI ALIQUIP IN DO ID EX DOLORE SINT REPREHENDERIT
Output
LOREM IPSUM DOLOR SIT AMET CONSECTETUR ADIPISCING ELIT SED DO EIUSMOD TEMPOR INCIDIDUNT UT LABORE ET DOLORE MAGNA ALIQUA UT ENIM AD MINIM VENIAM QUIS NOSTRUD EXERCITATION ULLAMCO LABORIS NISI UT ALIQUIP EX EA COMMODO CONSEQUAT DUIS AUTE IRURE DOLOR IN REPREHENDERIT IN VOLUPTATE VELIT ESSE CILLUM DOLORE EU FUGIAT NULLA PARIATUR EXCEPTEUR SINT OCCAECAT CUPIDATAT NON PROIDENT SUNT IN CULPA QUI OFFICIA DESERUNT MOLLIT ANIM ID EST LABORUM
15 Performance 1 (70 words) val Validator
Input
LOREMIPSUMDOLORSITAMETCONSECTETURADIPISCINGELITSEDDOEIUSMODTEMPORINCIDIDUNTUTLABOREETDOLOREMAGNAALIQUAUTENIMADMINIMVENIAMQUISNOSTRUDEXERCITATIONULLAMCOLABORISNISIUTALIQUIPEXEACOMMODOCONSEQUATDUISAUTEIRUREDOLORINREPREHENDERITINVOLUPTATEVELITESSECILLUMDOLOREEUFUGIATNULLAPARIATUREXCEPTEURSINTOCCAECATCUPIDATATNONPROIDENTSUNTINCULPAQUIOFFICIADESERUNTMOLLITANIMIDESTLABORUM
MAGNA AD LABORE QUIS EA DOLOR IN NON UT VENIAM AMET ALIQUA ID NULLA IRURE CUPIDATAT EXERCITATION CONSECTETUR COMMODO VELIT UT TEMPOR VOLUPTATE NISI ADIPISCING QUI IN MINIM ENIM DO SED NOSTRUD DOLORE SIT DOLORE ESSE EU OCCAECAT ALIQUIP CULPA OFFICIA PROIDENT ET REPREHENDERIT EIUSMOD DESERUNT ANIM ELIT LABORUM EXCEPTEUR SINT EX MOLLIT IPSUM IN PARIATUR DOLOR DUIS CONSEQUAT ULLAMCO LABORIS LOREM SUNT AUTE EST INCIDIDUNT FUGIAT CILLUM UT
Output
LOREM IPSUM DOLOR SIT AMET CONSECTETUR ADIPISCING ELIT SED DO EIUSMOD TEMPOR INCIDIDUNT UT LABORE ET DOLORE MAGNA ALIQUA UT ENIM AD MINIM VENIAM QUIS NOSTRUD EXERCITATION ULLAMCO LABORIS NISI UT ALIQUIP EX EA COMMODO CONSEQUAT DUIS AUTE IRURE DOLOR IN REPREHENDERIT IN VOLUPTATE VELIT ESSE CILLUM DOLORE EU FUGIAT NULLA PARIATUR EXCEPTEUR SINT OCCAECAT CUPIDATAT NON PROIDENT SUNT IN CULPA QUI OFFICIA DESERUNT MOLLIT ANIM ID EST LABORUM
16 Performance 2 (140 words) Test
Input
LOREMIPSUMDOLORSITAMETCONSECTETURADIPISCINGELITSEDDOEIUSMODTEMPORINCIDIDUNTUTLABOREETDOLOREMAGNAALIQUAESTLIBEROMOLESTIEACCUMSANDUIACRISUSINCEPTOSHABITASSEHABITASSEFINIBUSAORNAREINTERDUMVITAEHIMENAEOSAUGUEPHASELLUSSAPIENSITSOCIOSQUPHARETRAFINIBUSMORBIALIQUETTINCIDUNTCLASSESTDIAMHABITASSEFEUGIATMAGNAPROINMAURISVIVAMUSTINCIDUNTALIQUETNIBHALIQUAMACUBILIATELLUSLEOFELISALIQUAMVOLUTPATANTENAMVITAEDOLORPRETIUMTELLUSGRAVIDACONGUEALIQUETFAMESCONDIMENTUMNUNCNULLADIAMPRAESENTEGESTASTORTORALIQUETCONDIMENTUMFUSCEVULPUTATEPURUSINTERDUMMAURISULTRICESPULVINARFINIBUSNEQUELIGULALUCTUSNULLAMDAPIBUSBLANDITACDOLORVEHICULAMOLESTIELAOREETPLATEATINCIDUNTSAPIENPURUSNISLMOLLISIPSUMMINISIVELITHENDRERITSEDELEMENTUMCURABITURMAURISPHARETRAUTARCUSUSCIPITQUISVENENATISFAMESFEUGIATVELITNETUSBLANDITCONUBIAVELPROINPOSUEREVEHICULALAOREETCRASSEMPERMAXIMUSFINIBUS
PRETIUM DOLORE VEHICULA FINIBUS ET ALIQUAM VELIT MOLESTIE ALIQUET CONDIMENTUM MAURIS CONDIMENTUM PROIN LIBERO CRAS MI AC TINCIDUNT NISL HABITASSE VITAE EST MOLESTIE VEHICULA MOLLIS FAMES AMET NAM UT CLASS ANTE HIMENAEOS DIAM NUNC BLANDIT NETUS NIBH IPSUM SED A QUIS NEQUE SAPIENPURUS ULTRICES AC LOREM FAMES UT LAOREET SUSCIPIT ALIQUET VULPUTATE SEMPER ALIQUAM FELIS TELLUS NULLA TINCIDUNT INTERDUM CONGUE ALIQUET MAXIMUS NISI LEO POSUERE LIGULA FEUGIAT HABITASSE RISUS TEMPOR INTERDUM PROIN ADIPISCING FINIBUS PHARETRA TORTOR ELEMENTUM VELIT INCEPTOS VEL ELIT DOLOR A DO CONSECTETUR LUCTUS BLANDIT VENENATIS FEUGIAT MAGNA TELLUSGRAVIDA MAURIS VITAE PHARETRA SAPIEN ALIQUA CUBILIA DOLOR PULVINAR DUI LAOREET FINIBUS PURUS DIAM MORBI EIUSMOD PLATEA MAGNA CURABITUR ORNARE PRAESENT DOLOR NULLAM EGESTAS TINCIDUNT LABORE IPSUM CONUBIA FUSCE INCIDIDUNT SIT FINIBUS MAURIS VOLUTPAT ARCU AUGUE HENDRERIT SOCIOSQU HABITASSE SIT EST ACCUMSAN PHASELLUS SED ALIQUET VIVAMUS DAPIBUS
Output
LOREM IPSUM DOLOR SIT AMET CONSECTETUR ADIPISCING ELIT SED DO EIUSMOD TEMPOR INCIDIDUNT UT LABORE ET DOLORE MAGNA ALIQUA EST LIBERO MOLESTIE ACCUMSAN DUI AC RISUS INCEPTOS HABITASSE HABITASSE FINIBUS A ORNARE INTERDUM VITAE HIMENAEOS AUGUE PHASELLUS SAPIEN SIT SOCIOSQU PHARETRA FINIBUS MORBI ALIQUET TINCIDUNT CLASS EST DIAM HABITASSE FEUGIAT MAGNA PROIN MAURIS VIVAMUS TINCIDUNT ALIQUET NIBH ALIQUAM A CUBILIA TELLUS LEO FELIS ALIQUAM VOLUTPAT ANTE NAM VITAE DOLOR PRETIUM TELLUSGRAVIDA CONGUE ALIQUET FAMES CONDIMENTUM NUNC NULLA DIAM PRAESENT EGESTAS TORTOR ALIQUET CONDIMENTUM FUSCE VULPUTATE PURUS INTERDUM MAURIS ULTRICES PULVINAR FINIBUS NEQUE LIGULA LUCTUS NULLAM DAPIBUS BLANDIT AC DOLOR VEHICULA MOLESTIE LAOREET PLATEA TINCIDUNT SAPIENPURUS NISL MOLLIS IPSUM MI NISI VELIT HENDRERIT SED ELEMENTUM CURABITUR MAURIS PHARETRA UT ARCU SUSCIPIT QUIS VENENATIS FAMES FEUGIAT VELIT NETUS BLANDIT CONUBIA VEL PROIN POSUERE VEHICULA LAOREET CRAS SEMPER MAXIMUS FINIBUS
16 Performance 2 (140 words) val Validator
Input
LOREMIPSUMDOLORSITAMETCONSECTETURADIPISCINGELITSEDDOEIUSMODTEMPORINCIDIDUNTUTLABOREETDOLOREMAGNAALIQUAESTLIBEROMOLESTIEACCUMSANDUIACRISUSINCEPTOSHABITASSEHABITASSEFINIBUSAORNAREINTERDUMVITAEHIMENAEOSAUGUEPHASELLUSSAPIENSITSOCIOSQUPHARETRAFINIBUSMORBIALIQUETTINCIDUNTCLASSESTDIAMHABITASSEFEUGIATMAGNAPROINMAURISVIVAMUSTINCIDUNTALIQUETNIBHALIQUAMACUBILIATELLUSLEOFELISALIQUAMVOLUTPATANTENAMVITAEDOLORPRETIUMTELLUSGRAVIDACONGUEALIQUETFAMESCONDIMENTUMNUNCNULLADIAMPRAESENTEGESTASTORTORALIQUETCONDIMENTUMFUSCEVULPUTATEPURUSINTERDUMMAURISULTRICESPULVINARFINIBUSNEQUELIGULALUCTUSNULLAMDAPIBUSBLANDITACDOLORVEHICULAMOLESTIELAOREETPLATEATINCIDUNTSAPIENPURUSNISLMOLLISIPSUMMINISIVELITHENDRERITSEDELEMENTUMCURABITURMAURISPHARETRAUTARCUSUSCIPITQUISVENENATISFAMESFEUGIATVELITNETUSBLANDITCONUBIAVELPROINPOSUEREVEHICULALAOREETCRASSEMPERMAXIMUSFINIBUS
FUSCE VITAE TINCIDUNT MOLESTIE ELEMENTUM LAOREET ALIQUA NISI FEUGIAT AUGUE FEUGIAT VULPUTATE IPSUM PURUS TINCIDUNT ALIQUET ULTRICES IPSUM VELIT DOLOR DAPIBUS LABORE ALIQUET NUNC SIT DIAM PULVINAR MAURIS VEHICULA TINCIDUNT SEMPER VENENATIS FINIBUS AC SAPIENPURUS VOLUTPAT NETUS AMET PRAESENT ELIT TELLUS PRETIUM NULLAM CONUBIA CUBILIA INTERDUM NEQUE FINIBUS CRAS VELIT CONSECTETUR FINIBUS HIMENAEOS FINIBUS TELLUSGRAVIDA MAURIS A NULLA SOCIOSQU MAXIMUS LOREM BLANDIT ET HABITASSE HABITASSE LEO EIUSMOD DOLOR NISL BLANDIT ORNARE DO PHARETRA UT POSUERE VITAE CURABITUR ALIQUAM NIBH LIBERO CLASS FAMES ADIPISCING LIGULA A MOLESTIE SIT INCEPTOS SED VEHICULA DOLORE TORTOR ALIQUET AC PROIN PROIN RISUS EGESTAS EST HENDRERIT ANTE LAOREET NAM PHARETRA CONGUE HABITASSE MOLLIS DUI QUIS EST ACCUMSAN TEMPOR MI ALIQUET PHASELLUS INCIDIDUNT SAPIEN CONDIMENTUM LUCTUS SUSCIPIT INTERDUM ARCU SED FAMES ALIQUAM PLATEA DIAM MAGNA VEL MORBI FELIS VIVAMUS CONDIMENTUM MAGNA DOLOR UT MAURIS
Output
LOREM IPSUM DOLOR SIT AMET CONSECTETUR ADIPISCING ELIT SED DO EIUSMOD TEMPOR INCIDIDUNT UT LABORE ET DOLORE MAGNA ALIQUA EST LIBERO MOLESTIE ACCUMSAN DUI AC RISUS INCEPTOS HABITASSE HABITASSE FINIBUS A ORNARE INTERDUM VITAE HIMENAEOS AUGUE PHASELLUS SAPIEN SIT SOCIOSQU PHARETRA FINIBUS MORBI ALIQUET TINCIDUNT CLASS EST DIAM HABITASSE FEUGIAT MAGNA PROIN MAURIS VIVAMUS TINCIDUNT ALIQUET NIBH ALIQUAM A CUBILIA TELLUS LEO FELIS ALIQUAM VOLUTPAT ANTE NAM VITAE DOLOR PRETIUM TELLUSGRAVIDA CONGUE ALIQUET FAMES CONDIMENTUM NUNC NULLA DIAM PRAESENT EGESTAS TORTOR ALIQUET CONDIMENTUM FUSCE VULPUTATE PURUS INTERDUM MAURIS ULTRICES PULVINAR FINIBUS NEQUE LIGULA LUCTUS NULLAM DAPIBUS BLANDIT AC DOLOR VEHICULA MOLESTIE LAOREET PLATEA TINCIDUNT SAPIENPURUS NISL MOLLIS IPSUM MI NISI VELIT HENDRERIT SED ELEMENTUM CURABITUR MAURIS PHARETRA UT ARCU SUSCIPIT QUIS VENENATIS FAMES FEUGIAT VELIT NETUS BLANDIT CONUBIA VEL PROIN POSUERE VEHICULA LAOREET CRAS SEMPER MAXIMUS FINIBUS
Solution language
Solution
Stub generator input