Student Attendance Record I solution and explanation
Google
9 more videos on this problem
551. Student Attendance Record - Java || LeetCodeCoding Sphere · 4:49 · 1K views
551. Student Attendance Record I | LEETCODE EASYcode Explainer · 4:07 · 763 views
551. Student Attendance Record I (Leetcode Easy)Programming Live with Larry · 3:16 · 717 views
551. Student Attendance Record I || LEETCODE SOLUTION || IN C++ || DATA STRUCTURE AND ALGORITHMAbhishweta Gupta · 1:57 · 552 views
Leetcode 551 Student Attendance Record I (Java)TheAnalyticGuy · 3:17 · 314 views
LeetCode 551 : Student Attendance Record I || EASY || C++ || JAVA || Detailed SolutionCodeGPT · 10:15 · 261 views
551. Student Attendance Record I | Leetcode | PythonAbdullah Arshed · 2:47 · 241 views
How to Solve "551 Student Attendance Record I" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 6:39 · 124 views
551. Student Attendance Record I || In JAVA || Leetcode Problem || Easy #leetcodeQuick Learning With Sree · 9:01 · 122 views
LeetCode 551. Student Attendance Record I Solution Explained - JavaAlgorithms and Data Structures Course · 8:17 · 96 views
The problem
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 <= 1000s[i]is either'A','L', or'P'.
Approach overview
Problem Overview: You receive a string representing a student's attendance record. Each character is 'A' (Absent), 'L' (Late), or 'P' (Present). The record is valid if it contains fewer than two 'A' characters and never has three consecutive 'L' characters.
Approach 1: Single Pass Check (O(n) time, O(1) space)
Scan the string once while tracking two things: the total number of absences and the current streak of consecutive late days. Increment the absence counter whenever you see 'A'. For 'L', increment a running streak counter; reset it to zero when you encounter 'A' or 'P'. The moment the absence count reaches 2 or the late streak reaches 3, the record is invalid and you can return early. This approach works because the rules depend only on local counts, so a single linear iteration over the string captures everything needed.
The key insight is that you do not need additional data structures. Two integer counters are enough to enforce both constraints. Since each character is processed exactly once, the runtime is O(n), and the memory usage stays O(1). This is the standard interview solution because it is simple, efficient, and easy to reason about.
Approach 2: Regular Expression Matching (O(n) time, O(1) space)
The rules can also be expressed as a pattern check using regular expressions. A record becomes invalid if it matches either of these patterns: two absences anywhere (A.*A) or three consecutive lates (LLL). With regex support, you simply test whether the string matches A.*A|LLL. If it does, the attendance record violates the rules.
This approach is concise and expressive. It shifts the pattern detection to the regex engine instead of manual iteration. Under typical implementations, the scan still runs in O(n) time because the engine processes the string linearly. Space usage remains O(1) aside from minimal regex overhead. It is convenient in languages with strong regex support such as Python, Java, and JavaScript, though interviewers usually expect the manual scan.
Recommended for interviews: The single-pass counter approach is what interviewers expect. It demonstrates clear reasoning about constraints, efficient iteration over a string, and constant space usage. The regex version is elegant for quick scripting, but the explicit scan better shows algorithmic thinking and control over edge cases.
Approach 1: Single Pass Check
This approach involves a single traversal of the string, during which we track the count of 'A's and check for any sequence of 'L's greater than or equal to 3. If any of the conditions for disqualification is met, we terminate early.
class Solution:
def checkRecord(self, s: str) -> bool:
countA = 0
lenL = 0
for c in s:
if c == 'A':
countA += 1
if countA >= 2:
return False
if c == 'L':
lenL += 1
if lenL >= 3:
return False
else:
lenL = 0
return Trueclass Solution {
public boolean checkRecord(String s) {
int countA = 0, lenL = 0;
for (char c : s.toCharArray()) {
if (c == 'A') {
countA++;
if (countA >= 2) return false;
}
if (c == 'L') {
lenL++;
if (lenL >= 3) return false;
} else {
lenL = 0;
}
}
return true;
}
}#include <string>
class Solution {
public:
bool checkRecord(std::string s) {
int countA = 0;
int lenL = 0;
for (char c : s) {
if (c == 'A') {
countA++;
if (countA >= 2) return false;
}
if (c == 'L') {
lenL++;
if (lenL >= 3) return false;
} else {
lenL = 0;
}
}
return true;
}
};var checkRecord = function(s) {
let countA = 0, lenL = 0;
for (let c of s) {
if (c === 'A') {
countA++;
if (countA >= 2) return false;
}
if (c === 'L') {
lenL++;
if (lenL >= 3) return false;
} else {
lenL = 0;
}
}
return true;
};#include <stdbool.h>
#include <string.h>
bool checkRecord(char * s) {
int countA = 0;
int lenL = 0;
for (int i = 0; s[i] != '\0'; ++i) {
if (s[i] == 'A') {
countA++;
if (countA >= 2) return false;
}
if (s[i] == 'L') {
lenL++;
if (lenL >= 3) return false;
} else {
lenL = 0;
}
}
return true;
}public class Solution {
public bool CheckRecord(string s) {
int countA = 0, lenL = 0;
foreach (char c in s) {
if (c == 'A') {
countA++;
if (countA >= 2) return false;
}
if (c == 'L') {
lenL++;
if (lenL >= 3) return false;
} else {
lenL = 0;
}
}
return true;
}
}The Python solution iterates over the string using a for-loop. We maintain and evaluate a counter for 'A' and the length of consecutive 'L's. Any violation of conditions results in an early false return.
Time Complexity: O(n) where n is the length of the string, as we traverse the string once.
Space Complexity: O(1) since we use a constant amount of space.
Approach 2: Regular Expression Matching
This approach uses pattern matching to detect invalid attendance records. We utilize regular expressions to verify that no segment of 3 'L's exists and that the count of 'A's is within the acceptable limit.
import re
class Solution:
def checkRecord(self, s: str) -> bool:
return not (len(re.findall('A', s)) >= 2 or 'LLL' in s)import java.util.regex.*;
class Solution {
public boolean checkRecord(String s) {
return !(Pattern.compile("A").matcher(s).results().count() >= 2 || s.contains("LLL"));
}
}var checkRecord = function(s) {
return !(s.split('').filter(c => c === 'A').length >= 2 || s.includes('LLL'));
};The Python solution leverages the built-in re module to perform regex operations. It counts 'A' occurrences and checks the presence of 'LLL' directly using regex.
Time Complexity: O(n) primarily due to the traversal to count 'A's and check for 'LLL'.
Space Complexity: O(1), though the re module might use additional space depending on implementation.
Approach 3: Default Approach
function checkRecord(s: string): boolean {
return s.indexOf('A') === s.lastIndexOf('A') && s.indexOf('LLL') === -1;
}func checkRecord(s string) bool {
return strings.Count(s, "A") < 2 && !strings.Contains(s, "LLL")
}Complexity comparison
| Approach | Complexity |
|---|---|
| Single Pass Check | Time Complexity: O(n) where n is the length of the string, as we traverse the string once. |
| Regular Expression Matching | Time Complexity: O(n) primarily due to the traversal to count 'A's and check for 'LLL'. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Single Pass Check | O(n) | O(1) | Best general solution. Preferred in coding interviews due to simplicity and constant memory. |
| Regular Expression Matching | O(n) | O(1) | Useful when regex support is strong and you want a concise pattern-based validation. |
Frequently asked questions
Is Student Attendance Record I easy or hard?
Student Attendance Record I is categorized as an Easy problem on LeetCode. The challenge focuses on careful string iteration and constraint checking rather than advanced data structures or algorithms.
Student Attendance Record I Python/Java solution
In Python or Java, the typical solution iterates through the string and maintains two counters: one for 'A' occurrences and one for consecutive 'L' characters. If the absence count reaches two or the late streak reaches three, the function returns false. The same O(n) logic applies across Python, Java, C++, and JavaScript.
How to solve Student Attendance Record I in O(n)?
Iterate through the string once while maintaining two variables: an absence counter and a consecutive late counter. Increment the absence counter for 'A'. Increment the late streak for 'L' and reset it for other characters. If absences reach 2 or the late streak reaches 3, return false; otherwise return true after the scan.
What is the best approach for Student Attendance Record I?
The best approach is a single-pass scan of the string while tracking two counters: total absences and the current consecutive late streak. If absences reach 2 or the late streak reaches 3, the record is invalid. This method runs in O(n) time and O(1) space and is the solution most interviewers expect.
Is Student Attendance Record I asked at Google/Amazon/Meta?
This problem represents a common string validation pattern often used in interviews at companies like Amazon and other large tech firms. While the exact question may vary, the underlying concept of scanning a string and enforcing constraints with counters appears frequently in coding interviews.
What data structure is used in Student Attendance Record I?
No complex data structure is required. The solution works directly on the input string with simple integer counters to track absences and consecutive late days. This keeps memory usage constant and the implementation straightforward.
What is the time complexity of Student Attendance Record I?
The optimal solution runs in O(n) time where n is the length of the attendance string. Each character is processed once while maintaining counters for absences and consecutive late days. Space complexity is O(1) because only a few integer variables are required.