Count longest subsequence in string
Last updated: November 25, 2025
Quick Overview
Given a string, write a function to count the length of the longest subsequence that can be formed from the characters of the string. A subsequence is defined as a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. The function should take a single string input and return an integer representing the length of the longest subsequence.
Grafana Labs
November 25, 20255
13
1,044 solved
Given a string, write a function to count the length of the longest subsequence that can be formed from the characters of the string. A subsequence is defined as a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. The function should take a single string input and return an integer representing the length of the longest subsequence.
This coding problem is frequently asked during Technical Screen at Grafana Labs. The interviewer is testing your ability to translate a problem into clean, working code while discussing time and space complexity. Grafana Labs expects candidates to write production-quality code, not just solve the puzzle.
What the Interviewer Expects
- Identify the correct data structure and algorithm for the problem
- Write clean, bug-free code with proper variable naming
- Analyze time and space complexity correctly
- Handle basic edge cases (empty input, single element)
- Communicate your thought process while coding
Key Topics to Cover
How to Approach This
- Clarify input constraints and edge cases before writing code.
- Walk through your approach verbally and confirm with the interviewer before coding.
- Start with a brute force solution, then optimize. Mention time and space complexity.
- Test your solution with examples, including edge cases like empty input or duplicates.
- Consider common patterns: sliding window, two pointers, hash map, BFS/DFS, dynamic programming.
Possible Follow-up Questions
- How would you parallelize this solution?
- Can you optimize the space complexity of your solution?
- What if the input doesn't fit in memory?
- What is the worst-case input for your solution?
Sharpen Your Skills on Codemia
Practice similar problems with our interactive workspace, get AI feedback, and track your progress.
Practice DSA ProblemsSample Answer
Problem Analysis
To solve the problem of counting the length of the longest subsequence in a string, we need to recognize that a subsequence is formed by taking characters from the string while maintaining their relat...
Approach
- Initialize a DP Array: Create an array
dpwheredp[i]will store the length of the longest subsequence that can be formed using the firsticharacters of the input string. - *Base Case...
Submit Your Answer
