FastPrep
Problem · Dynamic Programming

Transform String (Google India)

Learn this problem
● HardGoogleFULLTIMEPHONE SCREEN
See Google hiring insights

Problem statement

Given two strings of equal length made up of 'x', 'y', and 'z', with no consecutive characters the same, determine the minimum number of operations needed to transform the first string into the second. In one operation, you can change any character in the first string, ensuring no consecutive characters become identical.

Function

transformString(str1: String, str2: String) → int

Examples

Example 1

str1 = "zxyz"str2 = "zyxz"return = 6
One shortest valid sequence is zxyz → yxyz → yzyz → yzxz → zxzx → zxyz → zyxz.

Example 2

str1 = "xyzyzyxyzx"str2 = "xzyzyzyxzy"return = 15
The minimum number of valid one-character changes is 15.

Example 3

str1 = "xyxyxyxyxy"str2 = "xzyxyxzyxz"return = 13
The minimum number of valid one-character changes is 13.

Example 4

str1 = "xyxyzyzyxy"str2 = "zyzyxzyzyz"return = 9
The minimum number of valid one-character changes is 9.

Example 5

str1 = "xzxyxyzyzyxyzx"str2 = "zyzyxzyzyzyxzy"return = 20
The minimum number of valid one-character changes is 20.

Constraints

  • str1.length == str2.length
  • Both strings are non-empty and contain only 'x', 'y', and 'z'.
  • Neither input string contains two equal adjacent characters.

More Google problems

drafts saved locally
public int transformString(String str1, String str2) {
  // write your code here
}
str1"zxyz"
str2"zyxz"
expected6
checking account