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'.
My Solution
We first scan the String once to count the number of ‘A’s. If the number of ‘A’s is greater than or equal to two, we return false right away. Then we use the sliding window technique to check for three consecutive ‘L’s. If the number of characters in s is less than 3, we return true. Otherwise we count the number of ‘L’s in the first 3 characters and then keep updating this count as we go through the string. If the number of ‘L’s at any point is equal to 3, we return false right away. Otherwise if the character at position i is ‘L’, we decrement our late count and increment i. Then we increment j and if the character at position j is ‘L’, we increment our late count. Finally if we reach the end of the string without seeing three consecutive ‘L’s, we return true.
Time complexity is O(n), where n is the length of s, because we scan the array twice, once for checking ‘A’s and once for checking for 3 consecutive ‘L’s. Space complexity is O(1) since we only requires constant extra space.
class Solution {
public boolean checkRecord(String s) {
int absent = 0;
int n = s.length();
int late = 0;
for (char c : s.toCharArray()) {
if (c == 'A') {
absent++;
}
}
if (absent >= 2) {
return false;
}
if (n < 3) {
return true;
}
for (int i = 0; i < 3; i++) {
if (s.charAt(i) == 'L') {
late++;
}
}
int i = 0;
int j = 2;
while (j < n) {
if (late >= 3) {
return false;
}
if (s.charAt(i) == 'L') {
late--;
}
i++;
j++;
if (j < n && s.charAt(j) == 'L') {
late++;
}
}
return true;
}
}