FastPrepFewest Changes So Neighbors Differ
Problems/Fewest Changes So Neighbors Differ

Fewest Changes So Neighbors Differ

Expedia logoExpedia● EasyINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: An Expedia SDE intern review lists this as the first of its two coding questions. The candidate had two interview rounds after the online assessment, with one coding question in each. For this one, the candidate had to change characters so that a character never repeats right after itself. Because the replacements were unrestricted, the candidate found it simple.

The report does not say what to return or which characters the string holds. Here, the string has only lowercase English letters. Each change swaps one character for any lowercase letter. You return the fewest changes needed. The length limit of 10^5 is also our choice.

Our version is about 75% the same as the reported question.

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) → int

Examples

Example 1

s = "hello"return = 1

Only 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 = 3

Change 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 = 3

The 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^5
  • s contains 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 SWE Intern Final Round: 126 Experiences (Part 1 of 6)

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)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int minChanges(String s) {
        // Write your code here.
    }
}
Checking account…