Count Special Strings
Updated
Problem statement
Imagine you're working with Amazon's data analysis team, specifically focusing on analyzing customer behavior through clickstream data. This data consists of sequences of user actions on the website, represented as binary strings. A '1' could represent a significant action (like adding an item to the cart or making a purchase), and a '0' could represent a less significant action (like browsing or viewing a product).
You are given a binary string s that represents a user's interaction history. A behavior pattern (substring) is considered "special" if the number of insignificant actions ('0's) equals the square of the number of significant actions ('1's) within that pattern. That is, a substring is special when cnt0 = cnt1 * cnt1, where cnt0 is the count of '0's and cnt1 is the count of '1's in the substring.
The challenge is to identify and count all "special" behavior patterns in the user's interaction history. These patterns might indicate critical points in the user's journey where their browsing behavior was well-balanced with key actions, which could be important for understanding user engagement or predicting future purchases.
Only non-empty substrings are counted, and substrings are counted by position, so equal text at two different places counts twice. Index notation s[i,j] in the examples refers to the inclusive-inclusive substring spanning positions i through j (both endpoints included).
Function
countSpecialSubstrings(s: String) → int Complete the function countSpecialSubstrings in the editor.
countSpecialSubstrings has the following parameter:
String s: a binary string representing a user's interaction history
Returns int: the count of special behavior patterns (non-empty substrings)
Examples
Example 1
s = "010001"return = 4The special substrings are s[0,1] ("01"), s[1,2] ("10") and s[4,5] ("01"), which each have one '1' and one '0' (1 = 1 * 1), and the whole string s[0,5] ("010001"), which has two '1's and four '0's (4 = 2 * 2). No other substring works, so the answer is 4.
Example 2
s = "10010"return = 3The special binary substrings are s[0,1] ("10"), s[2,3] ("01"), and s[3,4] ("10"). Each has 1 significant action ('1') and 1 insignificant action ('0'), satisfying cnt0 = cnt1 * cnt1 (1 = 1 * 1).
Constraints
1 ≤ |s| ≤ 10^5sconsists of'0'and'1'only.
More Amazon interview questions
- Get Smallest Base SegmentOA · Seen Nov 2026
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Minimum Cost of Left and Right PropagationOA · Seen Nov 2026
- Minimum Grid InconvenienceOA · Seen Nov 2026
- 3SumPHONE SCREEN · Seen Nov 2026
- Circular Primes Below a LimitPHONE SCREEN · Seen Nov 2026
- Maximize K-Element AND with an Increment BudgetOA · Seen Nov 2026
- Maximize Shipment Order by Sorting One WindowOA · Seen Nov 2026
- Cheapest Flights Within K StopsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Shortest Digit Prefix for Target MultisetsVisa · OAVisa interview questions
- Longest Balanced Substring After One SwapTekion · OATekion interview questions
- Longest Substring with Even OccurrencesDeloitte · OADeloitte interview questions
- Extraordinary SubstringsPalantir · OAPalantir interview questions
- Number of Divisible Substrings (For MLE)Wayfair · OAWayfair interview questions
- Longest Equal-Frequency SubstringDRW · PHONE SCREENDRW interview questions
- Weighted Next-Word Prediction From Training SequencesGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Subscription and Usage-Based Billing CalculatorStripe · OAStripe interview questions
- Earliest Time to Schedule a MeetingMathWorks · OAMathWorks interview questions
- Count Subarrays with a Perfect-Square ProductMicrosoft · OAMicrosoft interview questions
Amazon interview experiences
- Amazon SWE OA with AI Coding: 1 Experience
- Amazon SWE Intern Phone Screen Interview Experience: 1 Experience
- Amazon New Grad SDE I OA and Virtual Onsite: 1 Experience
- Amazon BIE Intern SQL and Interview Questions: 17 Experiences
- Amazon Experienced SWE AI-Assisted Debugging OA: 1 Experience
- Amazon SDE II (L5) Interview Questions: 5 Experiences