algoadvance

Leetcode 551. Student Attendance Record I

Problem Statement

You are given a string s representing an attendance record for a student. The record only contains the following three characters:

A student could be rewarded if their attendance record doesn’t contain:

  1. More than one A (absent).
  2. More than two continuous L (late).

You need to implement a function bool checkRecord(string s) that returns true if the student’s attendance record is rewardable according to these criteria.

Clarifying Questions

  1. Should the function be case-sensitive?
    • No, we can assume the input string will only contain uppercase A, L, and P.
  2. Is the length of the string limited?
    • The length can be up to 100000.

Strategy

To solve this problem, we need to:

  1. Traverse the string s and count the occurrences of A. If it exceeds 1, return false.
  2. Simultaneously, check for any instance of three consecutive Ls. If found, return false.
  3. If neither condition is violated by the end of the string, return true.

We will iterate through the string once, making this approach linear in time complexity.

Code

Here’s the C++ implementation based on the outlined strategy:

#include <string>

using namespace std;

bool checkRecord(string s) {
    int aCount = 0;  // To count 'A's
    int lStreak = 0;  // To count consecutive 'L's

    for (char c : s) {
        if (c == 'A') {
            aCount++;
            if (aCount > 1) return false;
        }
        if (c == 'L') {
            lStreak++;
            if (lStreak > 2) return false;
        } else {
            lStreak = 0;  // Reset streak if it's not 'L'
        }
    }

    return true;
}

Time Complexity

The time complexity of this approach is O(n), where n is the length of the input string s. We make a single pass through the string to count the occurrences of ‘A’ and check for streaks of ‘L’. The space complexity is O(1), as we are only using a few extra integer variables for counting.

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