Fewest Changes So Neighbors Differ
Updated
Problem statement
You are given a string s of lowercase English letters. In one change, you may replace any single character of s with any lowercase English letter.
Return the minimum number of changes needed so that no two adjacent characters of s are equal.
Function
minChanges(s: String) → intExamples
Example 1
s = "hello"return = 1Only the two ls are next to each other. Changing one of them, for example to get helao, fixes it with 1 change.
Example 2
s = "zzzzzz"return = 3Change the second, fourth and sixth letters, for example to get zazbza. Now no two neighbours match, so 3 changes are enough. Fewer is not possible: the pairs at positions 0-1, 2-3 and 4-5 share no position, and each pair holds two equal letters, so each needs its own change.
Example 3
s = "bookkeeper"return = 3The string has three places where a letter repeats: oo, kk and ee. These pairs do not overlap, so each one needs its own change. Three changes are enough, for example boakaeaper, so the answer is 3.
Constraints
1 <= s.length <= 10^5scontains only lowercase English letters.
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
- Longest Spoken PrefixElevenLabs · ONSITE INTERVIEWElevenLabs interview questions
- Worker Task Assignment Part 1 - Balance WorkloadStripe · ONSITE INTERVIEWStripe interview questions
- Wildcard MatchingTripjack · ONSITE INTERVIEWTripjack interview questions
- Rearrange a String So No Neighbors MatchThe D.E. Shaw Group · ONSITE INTERVIEWThe D.E. Shaw Group interview questions
- Reorganize a StringAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Longest-Match Tokenizer with Unknown SymbolsAnthropic · ONSITE INTERVIEWAnthropic interview questions
- Text JustificationGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Minimum Nonadjacent Flips for an Alternating Binary StringInfosys · ONSITE INTERVIEWInfosys interview questions
- Greedy and Beam Sentence DecodingMicrosoft · PHONE SCREEN · ONSITE INTERVIEWMicrosoft interview questions
- Shortest Sequence of Source SubsequencesPinterest · ONSITE INTERVIEWPinterest interview questions
Interview reports that mention this question
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)