Expand a Repeat-Encoded String
Updated
Problem statement
You are given an encoded string s. Decode it and return the result.
The encoding has one rule: k[text], where k is a positive whole number, stands for text written k times in a row. For example, 3[ab] stands for "ababab".
- Letters outside any brackets are copied as they are.
- Groups can be nested: the
textinside the brackets may itself contain groups, which are decoded first. - Digits appear only as counts, always right before a
[. Every[has a matching], and every group holds at least one letter.
Function
decodeString(s: String) → StringExamples
Example 1
s = "2[go]3[x]y"return = "gogoxxxy"2[go] becomes "gogo" and 3[x] becomes "xxx". The last letter y is not inside brackets, so it is copied once.
Example 2
s = "2[k3[e]]"return = "keeekeee"Decode the inner group first: 3[e] is "eee", so the outer group is 2[keee], which is "keeekeee".
Example 3
s = "a10[b]c"return = "abbbbbbbbbbc"The count can have more than one digit: 10[b] is ten copies of b, between the plain letters a and c.
Constraints
1 <= s.length <= 60scontains only lowercase English letters, digits and the square brackets[and], and it is a valid encoding as described above.- Every count
kis between 1 and 300 and has no leading zeros. - The decoded string has at most 5000 characters.
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Single-Pass S-Expression ParserBaseten · ONSITE INTERVIEWBaseten interview questions
- Decode StringBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Calculator with ParenthesesGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Basic CalculatorAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Evaluate an Arithmetic Expression with DivisionMotive · ONSITE INTERVIEWMotive interview questions
- Remove Parentheses from a Plus-Minus ExpressionOracle · PHONE SCREENOracle interview questions
- Parse a Partial JSON StreamListen Labs · PHONE SCREEN
- Decode StringCompass International Holdings · PHONE SCREENCompass International Holdings interview questions
- Decode StringAbridge · OAAbridge interview questions
- Parenthesized String CalculatorMeta · PHONE SCREENMeta interview questions
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)