Problem

Create a basic sentence checker that takes in a stream of characters and determines whether they form valid sentences. If a sentence is valid, the program should print it out.

We can consider a sentence valid if it conforms to the following rules:

  1. The sentence must start with a capital letter, followed by a lowercase letter or a space.
  2. All other characters must be lowercase letters, separators (,,;,:) or terminal marks (.,?,!,‽).
  3. There must be a single space between each word.
  4. The sentence must end with a terminal mark immediately following a word.

Examples

Example 1

1
2
3

Input: "Hello world!"
Output: "Hello world!"
Explanation: Valid sentence - starts with capital, has single space between words, ends with terminal mark.

Example 2

1
2
3

Input: "hello world!"
Output: (no output)
Explanation: Invalid - doesn't start with capital letter.

Example 3

1
2
3

Input: "Hello  world!"
Output: (no output)
Explanation: Invalid - has double space between words.

Example 4

1
2
3

Input: "Hello, world; how are you?"
Output: "Hello, world; how are you?"
Explanation: Valid - contains separators and proper formatting.

Example 5

1
2
3

Input: "Hello world"
Output: (no output)
Explanation: Invalid - doesn't end with terminal mark.

Example 6

1
2
3

Input: "Hello World!"
Output: (no output)
Explanation: Invalid - 'World' starts with capital (should be lowercase).

Solution

Method 1 - State Machine Validation

Intuition

We can model this problem as a finite state machine where we track the current state of sentence parsing. The key insight is that we need to validate characters sequentially while maintaining context about what characters are expected next based on the current position in the sentence.

Approach

  1. Define states: START, FIRST_CHAR, WORD, SPACE, SEPARATOR, TERMINAL
  2. For each character, check if it’s valid for the current state
  3. Transition to the next appropriate state
  4. Track if we’ve seen any invalid transitions
  5. A sentence is valid only if it ends in TERMINAL state with no invalid transitions

Key validation rules:

  • First character must be uppercase letter
  • Second character must be lowercase letter or space
  • Words consist only of lowercase letters
  • Single spaces separate words
  • Separators can appear after words
  • Terminal marks must follow words directly

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

class Solution {
public:
    bool isValidSentence(string s) {
        if (s.empty()) return false;
        
        enum State { START, FIRST_CHAR, WORD, SPACE, SEPARATOR, TERMINAL };
        State state = START;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s[i];
            
            switch (state) {
                case START:
                    if (isupper(c)) {
                        state = FIRST_CHAR;
                    } else {
                        return false;
                    }
                    break;
                    
                case FIRST_CHAR:
                    if (islower(c)) {
                        state = WORD;
                    } else if (c == ' ') {
                        return false; // Space after single capital letter
                    } else if (isTerminal(c)) {
                        state = TERMINAL;
                    } else {
                        return false;
                    }
                    break;
                    
                case WORD:
                    if (islower(c)) {
                        // Stay in WORD
                    } else if (c == ' ') {
                        state = SPACE;
                    } else if (isSeparator(c)) {
                        state = SEPARATOR;
                    } else if (isTerminal(c)) {
                        state = TERMINAL;
                    } else {
                        return false;
                    }
                    break;
                    
                case SPACE:
                    if (islower(c)) {
                        state = WORD;
                    } else {
                        return false; // No double spaces or other chars after space
                    }
                    break;
                    
                case SEPARATOR:
                    if (c == ' ') {
                        state = SPACE;
                    } else if (islower(c)) {
                        state = WORD;
                    } else if (isTerminal(c)) {
                        state = TERMINAL;
                    } else {
                        return false;
                    }
                    break;
                    
                case TERMINAL:
                    return false; // Nothing should follow terminal
            }
        }
        
        return state == TERMINAL;
    }
    
private:
    bool isSeparator(char c) {
        return c == ',' || c == ';' || c == ':';
    }
    
    bool isTerminal(char c) {
        return c == '.' || c == '?' || c == '!' || c == '‽';
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

func isValidSentence(s string) bool {
    if len(s) == 0 {
        return false
    }
    
    const (
        START = iota
        FIRST_CHAR
        WORD
        SPACE
        SEPARATOR
        TERMINAL
    )
    
    state := START
    
    for i, c := range s {
        switch state {
        case START:
            if c >= 'A' && c <= 'Z' {
                state = FIRST_CHAR
            } else {
                return false
            }
            
        case FIRST_CHAR:
            if c >= 'a' && c <= 'z' {
                state = WORD
            } else if c == ' ' {
                return false
            } else if isTerminal(c) {
                state = TERMINAL
            } else {
                return false
            }
            
        case WORD:
            if c >= 'a' && c <= 'z' {
                // Stay in WORD
            } else if c == ' ' {
                state = SPACE
            } else if isSeparator(c) {
                state = SEPARATOR
            } else if isTerminal(c) {
                state = TERMINAL
            } else {
                return false
            }
            
        case SPACE:
            if c >= 'a' && c <= 'z' {
                state = WORD
            } else {
                return false
            }
            
        case SEPARATOR:
            if c == ' ' {
                state = SPACE
            } else if c >= 'a' && c <= 'z' {
                state = WORD
            } else if isTerminal(c) {
                state = TERMINAL
            } else {
                return false
            }
            
        case TERMINAL:
            return false
        }
    }
    
    return state == TERMINAL
}

func isSeparator(c rune) bool {
    return c == ',' || c == ';' || c == ':'
}

func isTerminal(c rune) bool {
    return c == '.' || c == '?' || c == '!' || c == '‽'
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

class Solution {
    private enum State {
        START, FIRST_CHAR, WORD, SPACE, SEPARATOR, TERMINAL
    }
    
    public boolean isValidSentence(String s) {
        if (s.isEmpty()) return false;
        
        State state = State.START;
        
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            
            switch (state) {
                case START:
                    if (Character.isUpperCase(c)) {
                        state = State.FIRST_CHAR;
                    } else {
                        return false;
                    }
                    break;
                    
                case FIRST_CHAR:
                    if (Character.isLowerCase(c)) {
                        state = State.WORD;
                    } else if (c == ' ') {
                        return false;
                    } else if (isTerminal(c)) {
                        state = State.TERMINAL;
                    } else {
                        return false;
                    }
                    break;
                    
                case WORD:
                    if (Character.isLowerCase(c)) {
                        // Stay in WORD
                    } else if (c == ' ') {
                        state = State.SPACE;
                    } else if (isSeparator(c)) {
                        state = State.SEPARATOR;
                    } else if (isTerminal(c)) {
                        state = State.TERMINAL;
                    } else {
                        return false;
                    }
                    break;
                    
                case SPACE:
                    if (Character.isLowerCase(c)) {
                        state = State.WORD;
                    } else {
                        return false;
                    }
                    break;
                    
                case SEPARATOR:
                    if (c == ' ') {
                        state = State.SPACE;
                    } else if (Character.isLowerCase(c)) {
                        state = State.WORD;
                    } else if (isTerminal(c)) {
                        state = State.TERMINAL;
                    } else {
                        return false;
                    }
                    break;
                    
                case TERMINAL:
                    return false;
            }
        }
        
        return state == State.TERMINAL;
    }
    
    private boolean isSeparator(char c) {
        return c == ',' || c == ';' || c == ':';
    }
    
    private boolean isTerminal(char c) {
        return c == '.' || c == '?' || c == '!' || c == '‽';
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

class Solution:
    def is_valid_sentence(self, s: str) -> bool:
        if not s:
            return False
        
        START, FIRST_CHAR, WORD, SPACE, SEPARATOR, TERMINAL = 0, 1, 2, 3, 4, 5
        state = START
        
        for c in s:
            if state == START:
                if c.isupper():
                    state = FIRST_CHAR
                else:
                    return False
                    
            elif state == FIRST_CHAR:
                if c.islower():
                    state = WORD
                elif c == ' ':
                    return False
                elif self._is_terminal(c):
                    state = TERMINAL
                else:
                    return False
                    
            elif state == WORD:
                if c.islower():
                    pass  # Stay in WORD
                elif c == ' ':
                    state = SPACE
                elif self._is_separator(c):
                    state = SEPARATOR
                elif self._is_terminal(c):
                    state = TERMINAL
                else:
                    return False
                    
            elif state == SPACE:
                if c.islower():
                    state = WORD
                else:
                    return False
                    
            elif state == SEPARATOR:
                if c == ' ':
                    state = SPACE
                elif c.islower():
                    state = WORD
                elif self._is_terminal(c):
                    state = TERMINAL
                else:
                    return False
                    
            elif state == TERMINAL:
                return False
        
        return state == TERMINAL
    
    def _is_separator(self, c: str) -> bool:
        return c in ',;:'
    
    def _is_terminal(self, c: str) -> bool:
        return c in '.?!‽'

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the input string. We process each character exactly once.
  • 🧺 Space complexity: O(1), as we only use a constant amount of extra space for state tracking.

Method 2 - Pattern Matching with Regular Expressions

Intuition

We can use regular expressions to define the exact pattern that a valid sentence must match. This approach is more concise but potentially less efficient for streaming data.

Approach

  1. Define a regex pattern that captures all the rules:
    • Starts with uppercase letter
    • Followed by lowercase letters and valid separators
    • Proper spacing rules
    • Ends with terminal mark
  2. Match the entire string against this pattern
  3. Return true if it matches completely

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
    bool isValidSentence(string s) {
        if (s.empty()) return false;
        
        // Pattern explanation:
        // ^[A-Z] - starts with capital letter
        // ([a-z]+([,;:]?( [a-z]+)*))? - optional word with separators and spaces
        // [.?!‽]$ - ends with terminal mark
        regex pattern("^[A-Z]([a-z]+([,;:]?( [a-z]+)*)?)*[.?!‽]$");
        return regex_match(s, pattern);
    }
};
1
2
3
4
5
6
7
8

class Solution {
    public boolean isValidSentence(String s) {
        if (s.isEmpty()) return false;
        
        String pattern = "^[A-Z]([a-z]+([,;:]?( [a-z]+)*)?)*[.?!‽]$";
        return s.matches(pattern);
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def is_valid_sentence(self, s: str) -> bool:
        if not s:
            return False
        
        import re
        pattern = r"^[A-Z]([a-z]+([,;:]?( [a-z]+)*)?)*[.?!‽]$"
        return bool(re.match(pattern, s))

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the input string. Regular expression matching is typically linear for simple patterns.
  • 🧺 Space complexity: O(1), excluding the space used by the regex engine for compilation.

Method 3 - Streaming Character Processor

Intuition

For streaming applications, we need to process characters one by one and maintain state between calls. This approach is most suitable when characters arrive incrementally rather than as a complete string.

Approach

  1. Maintain a sentence buffer and validation state
  2. Process each character as it arrives
  3. When a terminal mark is encountered, validate the complete sentence
  4. Reset state after processing each sentence
  5. Handle edge cases like empty sentences or invalid character sequences

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

class Solution {
private:
    string buffer;
    bool valid;
    
public:
    Solution() : valid(true) {}
    
    void processChar(char c) {
        buffer += c;
        
        if (isTerminal(c)) {
            if (valid && isValidComplete()) {
                cout << buffer << endl;
            }
            reset();
        } else {
            valid = valid && isValidAtPosition(c, buffer.length() - 1);
        }
    }
    
private:
    bool isValidAtPosition(char c, int pos) {
        if (pos == 0) {
            return isupper(c);
        }
        
        if (pos == 1) {
            return islower(c) || c == ' ';
        }
        
        char prev = buffer[pos - 1];
        
        if (c == ' ') {
            return islower(prev) || isSeparator(prev);
        }
        
        if (islower(c)) {
            return prev != ' ' || buffer.length() > 2;
        }
        
        if (isSeparator(c)) {
            return islower(prev);
        }
        
        return false;
    }
    
    bool isValidComplete() {
        if (buffer.length() < 2) return false;
        char lastChar = buffer[buffer.length() - 2];
        return islower(lastChar);
    }
    
    void reset() {
        buffer.clear();
        valid = true;
    }
    
    bool isSeparator(char c) {
        return c == ',' || c == ';' || c == ':';
    }
    
    bool isTerminal(char c) {
        return c == '.' || c == '?' || c == '!' || c == '‽';
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

class Solution {
    private StringBuilder buffer;
    private boolean valid;
    
    public Solution() {
        buffer = new StringBuilder();
        valid = true;
    }
    
    public void processChar(char c) {
        buffer.append(c);
        
        if (isTerminal(c)) {
            if (valid && isValidComplete()) {
                System.out.println(buffer.toString());
            }
            reset();
        } else {
            valid = valid && isValidAtPosition(c, buffer.length() - 1);
        }
    }
    
    private boolean isValidAtPosition(char c, int pos) {
        if (pos == 0) {
            return Character.isUpperCase(c);
        }
        
        if (pos == 1) {
            return Character.isLowerCase(c) || c == ' ';
        }
        
        char prev = buffer.charAt(pos - 1);
        
        if (c == ' ') {
            return Character.isLowerCase(prev) || isSeparator(prev);
        }
        
        if (Character.isLowerCase(c)) {
            return prev != ' ' || buffer.length() > 2;
        }
        
        if (isSeparator(c)) {
            return Character.isLowerCase(prev);
        }
        
        return false;
    }
    
    private boolean isValidComplete() {
        if (buffer.length() < 2) return false;
        char lastChar = buffer.charAt(buffer.length() - 2);
        return Character.isLowerCase(lastChar);
    }
    
    private void reset() {
        buffer.setLength(0);
        valid = true;
    }
    
    private boolean isSeparator(char c) {
        return c == ',' || c == ';' || c == ':';
    }
    
    private boolean isTerminal(char c) {
        return c == '.' || c == '?' || c == '!' || c == '‽';
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution:
    def __init__(self):
        self.buffer: str = ""
        self.valid: bool = True
    
    def process_char(self, c: str) -> None:
        self.buffer += c
        
        if self._is_terminal(c):
            if self.valid and self._is_valid_complete():
                print(self.buffer)
            self._reset()
        else:
            self.valid = self.valid and self._is_valid_at_position(c, len(self.buffer) - 1)
    
    def _is_valid_at_position(self, c: str, pos: int) -> bool:
        if pos == 0:
            return c.isupper()
        
        if pos == 1:
            return c.islower() or c == ' '
        
        prev = self.buffer[pos - 1]
        
        if c == ' ':
            return prev.islower() or self._is_separator(prev)
        
        if c.islower():
            return prev != ' ' or len(self.buffer) > 2
        
        if self._is_separator(c):
            return prev.islower()
        
        return False
    
    def _is_valid_complete(self) -> bool:
        if len(self.buffer) < 2:
            return False
        last_char = self.buffer[-2]
        return last_char.islower()
    
    def _reset(self) -> None:
        self.buffer = ""
        self.valid = True
    
    def _is_separator(self, c: str) -> bool:
        return c in ',;:'
    
    def _is_terminal(self, c: str) -> bool:
        return c in '.?!‽'

Complexity

  • ⏰ Time complexity: O(1) per character, O(n) total for processing a sentence of length n.
  • 🧺 Space complexity: O(n), where n is the maximum length of a sentence (for the buffer storage).