551. Student Attendance Record I


You are given a string representing an attendance record for a student. The record only contains the following three characters:

  1. 'A' : Absent.
  2. 'L' : Late.
  3. 'P' : Present.

A student could be rewarded if his attendance record doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late).

You need to return whether the student could be rewarded according to his attendance record.

Example 1:

Input: "PPALLP"
Output: True

Example 2:

Input: "PPALLL"
Output: False


Solution

Approach #1 Simple Solution [Accepted]

One simple way of solving this problem is to count number of in the string and check whether the string is a substring of a given string. If number of is less than and is not a subtring of a given string then return , otherwise return .

method can be used to check substring in a string. It return the index within this string of the first occurrence of the specified character or -1, if the character does not occur.

Complexity Analysis

  • Time complexity : . Single loop and indexOf method takes time.
  • Space complexity : . Constant space is used.

Approach #2 Better Solution [Accepted]

Algorithm

One optimization of above method is to break the loop when count of becomes .

Complexity Analysis

  • Time complexity : . Single loop and indexOf method takes time.
  • Space complexity : . Constant space is used.

Approach #3 Single pass Solution (Without indexOf method) [Accepted]

Algorithm

We can solve this problem in a single pass without using indexOf method. In a single loop we can count number of and also check the substring in a given string.

Complexity Analysis

  • Time complexity : . Single loop upto string length is used.
  • Space complexity : . Constant space is used.

Approach #4 Using Regex [Accepted]

Algorithm

One interesting solution is to use regex to match the string. Java provides the java.util.regex package for pattern matching with regular expressions. A regular expression is a special sequence of characters that helps you match or find other strings or sets of strings, using a specialized syntax held in a pattern.

Following are the regex's used in this solution:

. : Matches any single character except newline.

* : Matches 0 or more occurrences of the preceding expression.

.* : Matches any string

a|b : Matches either a or b

method is used to check whether or not the string matches the given regular expression.

Regular Expression of the string containing two or more than two will be and the regular expression of the string containing substring will be . We can merge this two regex using and form a regex of string containing either more than one or containing substring . Then regex will look like: . We will return true only when the string doesn't matches this regex.

Complexity Analysis

  • Time complexity : . method takes time.

  • Space complexity : . No Extra Space is used.

Analysis written by: @vinod23

Submit Solution