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:
'A') for strictly fewer than 2 days total.'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'.The key idea in #551 Student Attendance Record I is to verify whether a student's attendance string satisfies two rules: the student must have fewer than two absences ('A') and must not contain three consecutive lates ('L'). Since the input is a simple string, the most efficient strategy is a single pass traversal.
While scanning the string, keep track of the total number of absences and maintain a counter for consecutive late days. Each time you encounter 'L', increment the consecutive counter; reset it whenever another character appears. If the absence count reaches two or the late counter reaches three, the record immediately becomes invalid.
This approach avoids extra data structures and processes each character once. Because of the linear scan and constant tracking variables, the algorithm runs in O(n) time with O(1) additional space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Single pass string traversal with counters | O(n) | O(1) |
NeetCodeIO
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.
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.
1#include <stdbool.h>
2#include <string.h>
3
4bool checkRecord(char * s) {
5 int countA = 0;
6 int lenL = 0;
7 for (int i = 0; s[i] != '\0'; ++i) {
8 if (s[i] == 'A') {
9 countA++;
10 if (countA >= 2) return false;
11 }
12 if (s[i] == 'L') {
13 lenL++;
14 if (lenL >= 3) return false;
15 } else {
16 lenL = 0;
17 }
18 }
19 return true;
20}The C solution uses a loop to iterate over the input string. We maintain a counter for 'A' and track consecutive 'L's. If we encounter two 'A's or three consecutive 'L's, we quickly return false. Otherwise, return true after loop completion.
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.
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.
1import re
2class Solution:
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this type of string validation problem appears frequently in coding interviews. It tests basic string traversal, condition checking, and the ability to maintain simple counters efficiently.
No complex data structure is required for this problem. Simple counters and a variable to track consecutive 'L' characters are sufficient while iterating through the string.
The optimal approach is a single pass scan of the string while tracking the number of 'A' characters and the current streak of consecutive 'L' characters. If absences reach two or consecutive lates reach three, the record is invalid. This method runs in O(n) time and O(1) space.
The problem states that a student cannot be late for three consecutive days. Tracking the streak of 'L' characters helps detect this condition immediately during traversal without additional processing.
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.