Connection Status:
Competition Arena > LuckyTicketSubstring

LuckyTicketSubstring

SRM 380 · 2007-12-04 · by gevak

SRM 380 · 2007-12-04 · by gevak · Simple Search, Iteration
Class Name: LuckyTicketSubstring
Return Type: int
Method Name: maxLength
Arg Types: (string)
Problem Statement

Problem Statement

A lucky ticket is an integer with exactly 2*n digits (written without leading zeroes), where the sum of the leftmost n digits is equal to the sum of the rightmost n digits.

You are given a String s, which contains only non-zero digits. Find the longest contiguous substring of s that is a lucky ticket and return its length. If there is no such lucky ticket, return 0 instead.

Constraints

  • s will contain between 1 and 50 characters, inclusive.
  • s will contain non-zero digits ('1'-'9') only.
Examples
0)
"123231"
Returns: 6

The entire string, 123231, is a lucky ticket because the first 3 digits sum up to 1+2+3=6, and the last 3 digits sum up to 2+3+1=6.

1)
"74233285"
Returns: 4

4233 is the longest lucky ticket here.

2)
"986561517416921217551395112859219257312"
Returns: 36
3)
"12345678986987654321123456789359876543211234567895"
Returns: 32
4)
"1"
Returns: 0
7)
"112"
Returns: 2

A lucky ticket must contain an even number of digits.

Submissions are judged against all 67 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class LuckyTicketSubstring with a public method int maxLength(string s) · 67 test cases · 2 s / 256 MB per case

Submitting as anonymous