Coupon Code Validator

Difficulty: Easy | Acceptance: 64.90% | Paid: No Topics: Array, Hash Table, String, Sorting

You are given a string couponCode. A coupon code is valid if it satisfies the following conditions:

1. The length of the string is exactly 7.
2. The string consists only of uppercase English letters (‘A’-‘Z’) and digits (‘0’-‘9’).
3. The string contains at least one digit.
4. The string contains no duplicate characters.
5. The characters in the string are in strictly increasing order (i.e., couponCode[i] < couponCode[i+1] for all valid i).

Return true if the coupon code is valid, otherwise return false.

• Examples
• Constraints
• Single Pass with Hash Set
• Sorting and Comparison

Examples

Example 1

Input:

code = ["SAVE20","","PHARMA5","SAVE@20"], businessLine = ["restaurant","grocery","pharmacy","restaurant"], isActive = [true,true,true,true]

Output:

["PHARMA5","SAVE20"]

Explanation: First coupon is valid.

Second coupon has empty code (invalid).

Third coupon is valid.

Fourth coupon has special character @ (invalid).

Example 2

Input:

code = ["GROCERY15","ELECTRONICS_50","DISCOUNT10"], businessLine = ["grocery","electronics","invalid"], isActive = [false,true,true]

Output:

["ELECTRONICS_50"]

Explanation: First coupon is inactive (invalid).

Second coupon is valid.

Third coupon has invalid business line (invalid).

Constraints

1 <= couponCode.length <= 100
couponCode consists of uppercase English letters and digits.

Single Pass with Hash Set

Intuition We can validate the coupon code by iterating through the string once. We check the length first, then iterate to verify character types, digit presence, uniqueness (using a Hash Set), and the strictly increasing order property simultaneously.

Steps

• Check if the length of couponCode is exactly 7. If not, return false.
• Initialize a boolean flag hasDigit to false and a Hash Set seen to track characters.
• Iterate through the string with an index i:
  • Check if the character is an uppercase letter or a digit. If not, return false.
  • If the character is a digit, set hasDigit to true.
  • If the character is already in seen, return false (duplicate found).
  • If i > 0 and the current character is less than or equal to the previous character, return false (not strictly increasing).
  • Add the character to seen.
• After the loop, return hasDigit.

class Solution:
    def isValid(self, couponCode: str) -> bool:
        if len(couponCode) != 7:
            return False
        
        seen = set()
        has_digit = False
        
        for i, c in enumerate(couponCode):
            # Check if character is valid (Upper or Digit)
            if not (c.isdigit() or ("A" <= c <= "Z")):
                return False
            
            if c.isdigit():
                has_digit = True
            
            # Check for duplicates
            if c in seen:
                return False
            
            # Check for strictly increasing order
            if i > 0 and couponCode[i - 1] >= c:
                return False
            
            seen.add(c)
            
        return has_digit

Complexity

• Time: O(n), where n is the length of the string. We iterate through the string once.
• Space: O(1), since the Hash Set size is bounded by the number of possible characters (constant 128 or 36).
• Notes: This is the most optimal approach as it checks all conditions in a single pass.

Sorting and Comparison

Intuition We can leverage sorting to check for both the order and duplicate conditions. If we sort the string, it should match the original string if the original was strictly increasing. Additionally, duplicates will be adjacent in the sorted string, making them easy to detect.

Steps

• Check if the length of couponCode is exactly 7. If not, return false.
• Iterate through the string to check if all characters are valid (uppercase or digit) and if at least one digit exists.
• Create a sorted copy of the string.
• Compare the sorted string with the original string. If they are not equal, the original was not strictly increasing (or had duplicates).
• Iterate through the sorted string to check for adjacent duplicates. If any are found, return false.
• If all checks pass, return true.

class Solution:
    def isValid(self, couponCode: str) -> bool:
        if len(couponCode) != 7:
            return False
        
        has_digit = False
        for c in couponCode:
            if not (c.isdigit() or ("A" <= c <= "Z")):
                return False
            if c.isdigit():
                has_digit = True
        
        if not has_digit:
            return False
        
        sorted_code = "".join(sorted(couponCode))
        
        # Check if strictly increasing (original must match sorted)
        if couponCode != sorted_code:
            return False
        
        # Check for duplicates (adjacent in sorted string)
        for i in range(len(sorted_code) - 1):
            if sorted_code[i] == sorted_code[i+1]:
                return False
                
        return True

Complexity

• Time: O(n log n), due to the sorting step.
• Space: O(n), to store the sorted copy of the string.
• Notes: This approach is less efficient than the single pass approach due to the sorting overhead, but it is conceptually simple.