algoadvance

Leetcode 2451. Odd String Difference

Problem Statement

You are given an array of strings words. Each string consists of lowercase English letters and has the same length.

We’ll define the difference value of a string as an array of integers, where each integer represents the difference between the ASCII values of consecutive characters in the string.

For example, the difference value of “abcd” is [b-a, c-b, d-c] which translates to [1, 1, 1].

Your task is to find and return the unique string within the array words based on these difference values. It is guaranteed that there is exactly one such unique string.

Clarifying Questions

  1. Format of input and output:
    • Input: An array of strings words
    • Output: A single string which is the unique one based on the difference values.
  2. Length of the strings:
    • All strings in words are of the same length.
  3. Guaranteed constraints:
    • There is exactly one unique string in terms of difference values.

Strategy

  1. Calculate Difference Values: For each string in the array, compute the difference value.
  2. Store Difference Values: Use a dictionary to store the difference value as the key and maintain a list of strings that have that particular difference.
  3. Identify Unique String:
    • Normally, strings with the same difference values should be grouped together.
    • The unique string will be the one whose difference value appears exactly once in the dictionary.
  4. Return the Unique String.

Code

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
using namespace std;

vector<int> getDifferenceValue(const string &s) {
    vector<int> diff;
    for (int i = 1; i < s.length(); ++i) {
        diff.push_back(s[i] - s[i - 1]);
    }
    return diff;
}

string oddStringDifference(vector<string>& words) {
    unordered_map<string, vector<string>> diffMap;
    
    for (const auto& word : words) {
        vector<int> diffVec = getDifferenceValue(word);
        string diffStr;
        for (const int& num : diffVec) {
            diffStr += to_string(num) + ",";
        }
        diffMap[diffStr].push_back(word);
    }
    
    for (const auto& entry : diffMap) {
        if (entry.second.size() == 1) {
            return entry.second[0];
        }
    }
    
    return ""; // This line should not be reached due to problem constraints
}

int main() {
    vector<string> words = {"adc", "wzy", "abc"};
    cout << oddStringDifference(words) << endl;
    return 0;
}

Time Complexity

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

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