algoadvance

Leetcode 3136. Valid Word

Problem Statement

Given a string sequence containing a sequence of houses represented by the character ‘H’ and spaces represented by the character ‘.’ between the houses, the goal is to determine if it’s possible to place electric poles in such a way that each house has an electric pole adjacent to it. Each house can either have an electric pole on its left or right side or on both sides. However, poles cannot be placed directly adjacent to each other except with a house between them (i.e., “HPH” is valid but “HPPH” is not).

Function signature:

bool validWordOut(string sequence);

Clarifying Questions

  1. What happens if there’s no space (‘.’) to place a pole?
    • The task is impossible, hence the function should return false.
  2. Can there be poles in the initial sequence?
    • No, the initial input only contains ‘H’ and ‘.’.
  3. Should we consider edge cases like an empty sequence or a sequence with only dots?
    • Yes, these should return true since there’s no constraint violation.

Strategy

  1. Iterate through the sequence:
    • Check each house (‘H’) and ensure that there is at least one space (‘.’) adjacent to it (either to the left or right).
    • Mark spaces where poles can be placed, and ensure no two poles get placed adjacent to each other except through a house (‘H’).
  2. Edge cases:
    • Handle empty sequences.
    • Handle sequences with only dots.
    • Handle sequences starting or ending with a house.

Code Implementation

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

bool validWordOut(string sequence) {
    int n = sequence.length();
    
    if (n == 0) return true; // An empty sequence is trivially valid

    // Iterate through each character and apply the validation logic
    for (int i = 0; i < n; ++i) {
        if (sequence[i] == 'H') {
            // Check the left and right sides for available spaces
            bool leftValid = (i > 0 && sequence[i - 1] == '.');
            bool rightValid = (i < n - 1 && sequence[i + 1] == '.');
            
            if (!leftValid && !rightValid) {
                return false; // No valid place for this 'H'
            }
        }
    }
    
    return true; // All houses can be provided with poles
}

int main() {
    // Test cases
    cout << validWordOut("H.H") << endl;      // Expected output: 1 (true)
    cout << validWordOut("HH") << endl;       // Expected output: 0 (false)
    cout << validWordOut("H..H") << endl;     // Expected output: 1 (true)
    cout << validWordOut(".") << endl;        // Expected output: 1 (true)
    cout << validWordOut("") << endl;         // Expected output: 1 (true)
    cout << validWordOut("H...H") << endl;    // Expected output: 1 (true)
    cout << validWordOut("H") << endl;        // Expected output: 0 (false)
    cout << validWordOut("H.H.H") << endl;    // Expected output: 1 (true)
    return 0;
}

Time Complexity

The time complexity of this solution is O(n), where n is the length of the sequence since we are iterating through the characters of the sequence exactly once to determine the validity of placement of poles.

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