Problem Description

The Leetcode problem Student Attendance Record I asks you to determine whether a student's attendance record meets certain criteria for being "acceptable." The attendance record is given as a string s consisting only of the characters 'A' (Absent), 'L' (Late), and 'P' (Present).

An attendance record is considered acceptable if:

• There are no more than one 'A' (Absent) in the record.
• The record does not contain three or more consecutive 'L' (Late).

The function should return true if the record is acceptable, and false otherwise.

Thought Process

Initially, one might think of checking each possible substring or counting every possible combination, which could be inefficient. However, the constraints are simple and direct:

• Count the number of 'A's. If it's more than 1, the record is invalid.
• Look for any sequence of three or more consecutive 'L's. If such a sequence exists, the record is invalid.

Solution Approach

Let's break down the solution step-by-step:

1. Initialize counters: Start with a counter for 'A's set to zero and another to keep track of consecutive 'L's.
2. Iterate through the string: For each character in the attendance record:
   • If the character is 'A', increment the 'A' counter. If it exceeds 1, return false immediately.
   • If the character is 'L', increment the consecutive 'L' counter. If it reaches 3, return false immediately.
   • If the character is not 'L' (i.e., 'A' or 'P'), reset the consecutive 'L' counter to zero.
3. Final check: If the loop completes without returning false, the record is acceptable, so return true.

Example Walkthrough

Let's consider the input s = "PPALLP":

1. Start with A_count = 0, L_streak = 0.
2. First character: 'P' → L_streak reset to 0.
3. Second character: 'P' → L_streak reset to 0.
4. Third character: 'A' → A_count = 1.
5. Fourth character: 'L' → L_streak = 1.
6. Fifth character: 'L' → L_streak = 2.
7. Sixth character: 'P' → L_streak reset to 0.

At no point did A_count exceed 1, and L_streak never reached 3. Therefore, the function should return true.

Now consider s = "PPALLL":

• The last three characters are all 'L', so L_streak will reach 3, and the function will return false at that point.

Time and Space Complexity

Brute-force approach: If we checked every possible substring for three L's, it would take O(n^2) time, where n is the length of the string.

Optimized approach: By scanning the string once and maintaining counters, we achieve O(n) time complexity, as every character is checked only once. Space complexity is O(1), since we only use a few variables regardless of the input size.

Code Implementation

class Solution:
    def checkRecord(self, s: str) -> bool:
        a_count = 0
        l_streak = 0
        for c in s:
            if c == 'A':
                a_count += 1
                if a_count > 1:
                    return False
                l_streak = 0
            elif c == 'L':
                l_streak += 1
                if l_streak >= 3:
                    return False
            else:
                l_streak = 0
        return True
      

class Solution {
public:
    bool checkRecord(string s) {
        int a_count = 0, l_streak = 0;
        for (char c : s) {
            if (c == 'A') {
                a_count++;
                if (a_count > 1) return false;
                l_streak = 0;
            } else if (c == 'L') {
                l_streak++;
                if (l_streak >= 3) return false;
            } else {
                l_streak = 0;
            }
        }
        return true;
    }
};
      

class Solution {
    public boolean checkRecord(String s) {
        int aCount = 0, lStreak = 0;
        for (char c : s.toCharArray()) {
            if (c == 'A') {
                aCount++;
                if (aCount > 1) return false;
                lStreak = 0;
            } else if (c == 'L') {
                lStreak++;
                if (lStreak >= 3) return false;
            } else {
                lStreak = 0;
            }
        }
        return true;
    }
}
      

var checkRecord = function(s) {
    let aCount = 0, lStreak = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === 'A') {
            aCount++;
            if (aCount > 1) return false;
            lStreak = 0;
        } else if (s[i] === 'L') {
            lStreak++;
            if (lStreak >= 3) return false;
        } else {
            lStreak = 0;
        }
    }
    return true;
};
      

Summary

To solve the Student Attendance Record I problem, we scan the attendance string once, counting absences and tracking consecutive lates. The solution is efficient (O(n) time, O(1) space), easy to understand, and avoids unnecessary complexity. The key insight is that both constraints can be checked in a single pass using simple counters, making the implementation both elegant and practical.