FastPrep
Problem · Greedy

Get Min Move 🐱

Learn this problem
● HardIBMFULLTIMEOA
See IBM hiring insights

Problem statement

An English lecture at HackerElementary School is aimed at teaching students the letters of alphbets.

The students are provided with a string word that consists of lowercase English letters. In one move, the can choose any index i, and let the character at the index be c. Then, the first occurrence of c to the left of i, and the first occurence of c to the right of i are deleted (Note: the operation can still be carried out even if either the left or right occurrence does not exist).

For example, if word = "adabacaea", and if index 8 is chosen (0-based), the first occurrence of 'a' to the left and right of index 4 (bold, indices 2 and 6) are deleted leaving word = "adbacea".

Find the min num of moves the students need to perform in order to get a word of minimal length.

Function

getMinMove(word: String) → int

Complete the function getMinMove in the editor below.

getMinMove has the following parameter(s):

  • String word: the word given to the students

    • Returns

    int: the min num of moves needed to get a word of minimal length

    Examples

    Example 1

    word = "baabacaa"return = 3
    The following moves are optional: 1. Choose index 0. "baabacaa", then word = "baaacaa". Delete the b to its right at index 3. There is no b to its left so the option is finished 2. Now, choose index 2. "baaacaa", then word = "bacaa". 3. Now, choose index 3. "bacaa", then word = "bca". The word cannot be reduced further. Return 3.

    Example 2

    word = "cbaa"return = 1
    Optimally, choose index 2, then word = "cba".

    Constraints

  • 1 <= |word| <= 105
  • The string word consists of lowercase English letters.

    • More IBM problems

    drafts saved locally
    public int getMinMove(String word) {
    // write your code here
}
    word"baabacaa"
    expected3
    checking account