Data Structure and Algorithm - Find the Longest Continuous Distinct Characters (Amazon Interview Question)

1. Problem Description

This is an Amazon interview question for software develop engineer from careercup. Here is the original thread

"

In a string detect the smallest window length with highest number of distinct characters. For eg. 

A = “aabcbcdbca”, then ans would be 4 as of “dbca”

- neer.1304 18 days ago in United States | Report Duplicate | Flag ".

2. Pseudo-code

String tempResult

String finalResult

HashSet hs

- 1. Check if this character, x, appears in hs. If yes,

    * assign tempResult to finalResult if tempResult is longer than finalResult

    * Remove entries in hs of the characters from the beginning to character x in tempResult

    * Remove the beginning to character x in tempResult

- 2. add this character into hs,

- 3. append this character into tempResult

- 4. Repeat 1,2 and 3 until reach the end of the input string

- 5. Swap tempResult and finalResult if tempResult is longer

3. C++ Implementation

// ********************************************************************************

// Implementation

// ********************************************************************************

#include <queue>

#include <string>

#include <unordered_set>

std::string FindLongestUniqueCharacterSerial(const std::string& input)

{

    if (input.empty()) {

        return std::string();

    }

    std::unordered_set<char> appearedCharacters;

    std::string uniqueCharacters;

    std::string result;

    auto iterEnd = input.end();

    for (auto iter = input.begin(); iter != iterEnd; ++iter) {

        if (appearedCharacters.find(*iter) != appearedCharacters.end()) {

            // The case of "yes", in Step 1

            if (uniqueCharacters.size() > result.size()) {

                result = uniqueCharacters;

            }

            auto iterUC = uniqueCharacters.begin();

            auto iterUCEnd = uniqueCharacters.end();

            for (; iterUC != iterUCEnd; ++iterUC) {

                if (*iterUC == *iter) {

                    break;

                }

                appearedCharacters.erase(*iterUC);

            }

            std::string(++iterUC, iterUCEnd).swap(uniqueCharacters);

        }

        // Step 2 and 3

        appearedCharacters.insert(*iter);

        uniqueCharacters.push_back(*iter);

    }

    // Step 5

    if (uniqueCharacters.size() > result.size()) {

        result.swap(uniqueCharacters);

    }

    return result;

}

// ********************************************************************************

// Test

// ********************************************************************************

#include <cassert>

void TestCasesOfFindLongestUniqueCharacterSerial()

{

    std::string testString;

    assert(FindLongestUniqueCharacterSerial(testString).empty());

    testString = "aaaaaaaaaaaaaaaaaaaa";

    assert(FindLongestUniqueCharacterSerial(testString) == "a");

    testString = "abcdefghijklmn";

    assert(FindLongestUniqueCharacterSerial(testString) == testString);

    testString = "aabcbcdbca";

    assert(FindLongestUniqueCharacterSerial(testString) == "dbca");

    testString = "bcccf";

    assert(FindLongestUniqueCharacterSerial(testString) == "bc");

}