algoadvance

Leetcode 2451. Odd String Difference

Problem Statement

You are given an array of strings words. Each string contains lower-case English letters of equal length. A string s is considered odd if and only if the difference between the ASCII values of every two consecutive characters is an odd value. Return the odd string from the array words. There will be exactly one string in the input list which meets the criteria.

Clarifying Questions

  1. Input Size:
    • What is the maximum length of each string in the words array?
    • What is the maximum number of strings in the words array?
  2. Output:
    • Should the function return only one string that matches the criteria, assuming there’s only one correct result?
  3. Edge Cases:
    • Should we consider edge cases such as empty strings or an empty input array, or is it guaranteed that the input will always be a non-empty array with non-empty strings?

Let’s assume from the statement that there is always exactly one string that meets the condition.

Strategy

  1. Iterate through the words array:
    • For each string, compute the absolute difference between the ASCII values of every two consecutive characters.
    • Check if all these differences are odd.
    • If a string meets this condition, return this string.

Code

Here is the implementation of the given problem in Java:

public class Solution {
    public String oddString(String[] words) {
        for (String word : words) {
            boolean isOdd = true; // flag to check if all differences are odd
            for (int i = 0; i < word.length() - 1; i++) {
                int diff = Math.abs(word.charAt(i) - word.charAt(i + 1));
                if (diff % 2 == 0) {
                    isOdd = false; // found an even difference
                    break;
                }
            }
            if (isOdd) {
                return word; // return the odd string
            }
        }
        return ""; // Default case, should not be reached
    }
}

Time Complexity

The time complexity of this solution can be analyzed as follows:

The solution involves:

Thus, the overall time complexity is O(n * m).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI