Consecutive Author Constraint — Problem Statement & Solution Guide

StringsMediumMixed

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Consecutive Author Constraint problem optimally.

TopicStrings

PatternMixed

TimeO(n)

SpaceO(1)

Problem Description

Given an integer array authors of length n, each element denotes the identifier of the author of a chapter. A subsequence is obtained by deleting zero or more elements without changing the order of the remaining ones. Determine the greatest possible length of a subsequence that satisfies two conditions: (1) any two consecutive elements in the subsequence have different author identifiers, and (2) the first and the last elements of the subsequence are not equal. If no subsequence meets both criteria, return 0.

DSA Pattern Breakdown

"Consecutive Author Constraint"

medium

WHY DOES IT MATTER?

This pattern exemplifies the greedy‑choice property where a locally optimal decision (taking a different author immediately) leads to a globally optimal solution, a cornerstone in many string and sequence problems.

OPTIMIZATION CHALLENGE

Recognizing that only the last chosen author influences the feasibility of the next choice eliminates the need for DP tables, collapsing the problem to a single pass.

REAL-WORLD CONNECTION

Think of a distributed logging system that must forward events to a consumer without sending two identical source IDs back‑to‑back to avoid throttling; the greedy filter mirrors the same logic.

During an interview, write the loop that updates a 'prev' variable first; it clarifies intent and avoids off‑by‑one bugs when handling the first element.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem reduces to constructing the longest subsequence with the property that adjacent elements differ. A greedy scan works because the decision to keep an element only depends on the previously chosen one: if the current author differs from the last selected author, keeping it can never hurt future choices, as any later element sees the same last‑selected author regardless of whether we skipped the current one. Naïve exhaustive search would try all 2^n subsets, exploding for n>30, and dynamic programming with O(n^2) transitions is unnecessary. The optimal paradigm is a linear‑time greedy algorithm that maintains the last author taken and increments the answer whenever a new distinct author appears.

Interview Questions on This Problem

Q1How would you compute the maximum length of a subsequence where no two consecutive authors are the same in O(n) time?

Iterate once through the array, keep a variable lastAuthor initialized to a sentinel. For each author, if it differs from lastAuthor, increment count and set lastAuthor to this author. The final count is the answer.

Q2If the array is [5,5,5,5], what is the longest valid subsequence length and why?

The length is 1 because any two selected elements would be consecutive with the same author, violating the constraint. The greedy algorithm picks the first 5 and then skips the rest.

Q3Can you extend the solution to handle an additional constraint that the subsequence must contain at most k occurrences of any author? How would the algorithm change?

Maintain a hash map counting occurrences of each author in the current subsequence. While scanning, only add the current author if it differs from the last selected author and its count is < k. This still runs in O(n) with O(m) extra space where m is the number of distinct authors.

Examples

Example 1

Input

6
1 2 2 3 1 4

Output

Explanation: One optimal subsequence is [1,2,3,1,4]. All adjacent pairs differ (1≠2, 2≠3, 3≠1, 1≠4) and the endpoints 1 and 4 are distinct, giving length 5. Any subsequence of length 6 would have to include both 2 s that are adjacent in the original array, violating condition 1, so 5 is maximal.

Example 2

Input

4
5 5 5 5

Output

Explanation: Every element has the same identifier. Any subsequence with more than one element would contain equal adjacent identifiers, breaking condition 1. A single‑element subsequence satisfies condition 1 but fails condition 2 because its first and last elements are identical. Hence no valid subsequence exists and the answer is 0.

Example 3

Input

7
1 2 3 4 5 6 7

Output

Explanation: All identifiers are distinct, so the whole array itself is a valid subsequence. Adjacent elements differ and the first element 1 is not equal to the last element 7, yielding the maximum possible length 7.

Constraints

1 <= authors.length <= 200000
1 <= authors[i] <= 10^9

Optimal Approach & Strategy

Traverse the array once, count an element only if it differs from the previously counted author.

Brute Force Approach

Try every subset of indices (2^n possibilities) and keep the longest one that satisfies the consecutive‑author rule.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function longestSubseq(authors) {
    if (authors.length === 0) return 0;
    let cnt = 1;
    for (let i = 1; i < authors.length; i++) {
        if (authors[i] !== authors[i-1]) cnt++;
    }
    return cnt;
}

const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length){
    const n = data[0];
    const arr = data.slice(1,1+n);
    console.log(longestSubseq(arr));
}

#include <bits/stdc++.h>
using namespace std;

int longestSubseq(const vector<int>& authors) {
    if(authors.empty()) return 0;
    int cnt = 1;
    for(size_t i=1;i<authors.size();++i){
        if(authors[i]!=authors[i-1]) ++cnt;
    }
    return cnt;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; if(!(cin>>n)) return 0;
    vector<int> a(n);
    for(int i=0;i<n;++i) cin>>a[i];
    cout<<longestSubseq(a);
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static int longestSubseq(int[] authors) {
        if (authors.length == 0) return 0;
        int cnt = 1;
        for (int i = 1; i < authors.length; i++) {
            if (authors[i] != authors[i-1]) cnt++;
        }
        return cnt;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        if (line == null || line.isEmpty()) return;
        int n = Integer.parseInt(line.trim());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        System.out.print(longestSubseq(arr));
    }
}

import sys

def longest_subseq(authors):
    """Return the maximum length of a subsequence with no equal consecutive authors."""
    if not authors:
        return 0
    cnt = 1
    for i in range(1, len(authors)):
        if authors[i] != authors[i-1]:
            cnt += 1
    return cnt

def main():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])
    arr = list(map(int, data[1:1+n]))
    print(longest_subseq(arr))

if __name__ == "__main__":
    main()

function longestSubseq(authors) {
    if (authors.length === 0) return 0;
    let cnt = 1;
    for (let i = 1; i < authors.length; i++) {
        if (authors[i] !== authors[i-1]) cnt++;
    }
    return cnt;
}

const fs = require('fs');
const data = fs.readFileSync(0,'utf8').trim().split(/\s+/).map(Number);
if(data.length){
    const n = data[0];
    const arr = data.slice(1,1+n);
    console.log(longestSubseq(arr));
}

Asked in Top Tech Interviews

Amazon

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.