Identifying the Odd One Out in a Series of Strings | Hackerrank

In certain scenarios, we may encounter a series of strings where all but one string possess similar characteristics. Our goal is to identify the odd one out from the given series. To tackle this problem, we will develop an algorithm and provide its implementation in Python and Java. We will also analyse the complexity of the algorithm and conclude with its efficiency.

Problem Description: Given a series of strings, each containing only uppercase English letters, we need to determine the odd one out. The odd one out is the string that significantly differs from the others in terms of the calculated distances between consecutive characters.

Algorithm:

To solve this problem, we can follow the below steps:

1. Initialise an empty list called `distances` to store the calculated distances for each string in the series.

2. Initialise an empty string called `odd_one_out` to store the odd one out.

3. Iterate over each string `s` in the series.

   - For each string `s`, calculate the distances between consecutive characters and store them in a list called `dist`.

   - Append the tuple representation of `dist` to the `distances` list.

4. Iterate over the `distances` list.

   - Check if the count of a particular distance tuple is equal to 1.

   - If so, assign the corresponding string from the series to `odd_one_out`.

   - Break the loop.

5. Return the `odd_one_out` string.

Pseudo Code:

Python Implementation:

def findOdd(series):

    distances = []

    odd_one_out = ""

    for s in series:

        dist = []

        for i in range(len(s)-1):

            dist.append(ord(s[i+1]) - ord(s[i]))

        distances.append(tuple(dist))

    for i in range(len(distances)):

        if distances.count(distances[i]) == 1:

            odd_one_out = series[i]

            break

    return odd_one_out

Java Implementation:

import java.util.ArrayList;

import java.util.List;

public class OddOneOut {

    public static String findOdd(String[] series) {

        List<List<Integer>> distances = new ArrayList<>();

        String oddOneOut = "";

        for (String s : series) {

            List<Integer> dist = new ArrayList<>();

            for (int i = 0; i < s.length() - 1; i++) {

                dist.add((int) s.charAt(i + 1) - (int) s.charAt(i));

            }

            distances.add(dist);

        }

        for (int i = 0; i < distances.size(); i++) {

            if (distances.stream().filter(dist -> dist.equals(distances.get(i))).count() == 1) {

                oddOneOut = series[i];

                break;

            }

        }

        return oddOneOut;

    }

    public static void main(String[] args) {

        String[] series = {"ACB", "BDC", "CED", "DEF"};

        String oddOneOut = findOdd(series);

        System.out.println("Odd One Out: " + oddOneOut);

    }

}

Complexity Analysis

1. Let `n` be the number of strings in the series, and `m` be the length of each string.

2. Calculating the distances between consecutive characters for each string takes O(n * m) time.

3. Checking the count of each distance tuple also takes O(n * m) time.

4. Therefore, the overall time complexity of the algorithm is O(n * m).

5. The space complexity is O(n * m) to store the `distances` list.

Conclusion:

In this article, we discussed an algorithm to identify the odd one out from a series of strings. We provided implementations of the algorithm in Python and Java, along with the corresponding pseudo code. The algorithm calculates the distances between consecutive characters in each string and compares them to find the odd one out. We also performed a complexity analysis, which showed that the algorithm has a time complexity of O(n * m). By utilising this algorithm, we can efficiently solve the problem of identifying the odd one out in a series of strings.