Scale Engineer

Student Attendance Record I

Easy
#0534Time: O(N), where N is the length of the string `s`. In the worst case, we iterate through the string once to count absences and a second time to check for "LLL", resulting in a linear time complexity.Space: O(1), as we only use a constant amount of extra space for counter variables.
Data structures
String

Prompt

You are given a string s representing an attendance record for a student where each character signifies whether the student was absent, late, or present on that day. The record only contains the following three characters:

  • 'A': Absent.
  • 'L': Late.
  • 'P': Present.

The student is eligible for an attendance award if they meet both of the following criteria:

  • The student was absent ('A') for strictly fewer than 2 days total.
  • The student was never late ('L') for 3 or more consecutive days.

Return true if the student is eligible for an attendance award, or false otherwise.

 

Example 1:

Input: s = "PPALLP"
Output: true
Explanation: The student has fewer than 2 absences and was never late 3 or more consecutive days.

Example 2:

Input: s = "PPALLL"
Output: false
Explanation: The student was late 3 consecutive days in the last 3 days, so is not eligible for the award.

 

Constraints:

  • 1 <= s.length <= 1000
  • s[i] is either 'A', 'L', or 'P'.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach involves iterating through the string twice. The first pass checks for the total number of absences, and the second pass checks for consecutive late days. This separation of concerns makes the code easy to read and understand, although it's not the most performant.

Algorithm

  • Pass 1: Check for Absences.
    1. Initialize absentCount = 0.
    2. Iterate through the string s. For each character c:
      • If c is 'A', increment absentCount.
    3. If absentCount >= 2, the student is not eligible, so return false.
  • Pass 2: Check for Consecutive Lates.
    1. Check if the string s contains the substring "LLL".
    2. If it does, the student is not eligible, so return false.
  • Conclusion.
    1. If both passes complete without returning false, the student is eligible. Return true.

Walkthrough

In this method, we tackle the two eligibility criteria separately in two distinct passes over the input string.

First, we check the condition for absences. We iterate through the string from beginning to end, maintaining a counter for the character 'A'. If the total count of 'A's is 2 or more, we know the student is not eligible, and we can immediately conclude the result is false.

If the first pass completes and the number of absences is acceptable (fewer than 2), we proceed to the second pass. In this pass, we check for consecutive lates. A straightforward way to do this is to use a built-in string searching function, like contains(), to check for the existence of the substring "LLL". If this substring is found, the student is not eligible, and we return false.

If the second pass also completes without finding "LLL", it means neither of the disqualifying conditions was met. Therefore, the student is eligible for the award, and we return true.

class Solution {    public boolean checkRecord(String s) {        // Pass 1: Check for total absences        int absentCount = 0;        for (int i = 0; i < s.length(); i++) {            if (s.charAt(i) == 'A') {                absentCount++;            }        }        if (absentCount >= 2) {            return false;        }         // Pass 2: Check for consecutive lates        if (s.contains("LLL")) {            return false;        }         return true;    }}

Complexity

Time

O(N), where N is the length of the string `s`. In the worst case, we iterate through the string once to count absences and a second time to check for "LLL", resulting in a linear time complexity.

Space

O(1), as we only use a constant amount of extra space for counter variables.

Trade-offs

Pros

  • The logic is simple and easy to follow because it checks each condition independently.

  • The code is clean and readable due to the separation of concerns.

Cons

  • It is not the most efficient solution as it requires scanning the string up to two times, whereas a single pass is sufficient.

Solutions

class Solution {public  boolean checkRecord(String s) {    return s.indexOf("A") == s.lastIndexOf("A") && !s.contains("LLL");  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem