Connection Status:
Competition Arena > SimilarPairs

SimilarPairs

TCCC07 Sponsor 3 · 2007-07-30 · by Mike Mirzayanov

TCCC07 Sponsor 3 · 2007-07-30 · by Mike Mirzayanov · Brute Force, Search
Class Name: SimilarPairs
Return Type: int
Method Name: howManyElements
Arg Types: (vector<string>, int)
Problem Statement

Problem Statement

You are given a String[] text. Concatenate all the elements to make one string. A pair of non-empty two non-overlapping substrings of equal length (A, B) is called k-similar if there are no more than k positions where A and B have different characters. Return the number of distinct strings that belong to at least one such pair.

Constraints

  • text will contain between 1 and 50 elements, inclusive.
  • Each element of text will contain between 1 and 50 characters, inclusive.
  • Each element of text will contain only lowercase letters ('a'..'z').
  • k will be between 0 and 2500, inclusive.
Examples
0)
{"abacd"}
1
Returns: 6

The following strings each belong to at least one similar pair: "a", "b", "c", "d", "ab", "ac".

1)
{"aaaa"}
0
Returns: 2
2)
{"abcdefgh"}
2
Returns: 15
3)
{"a", "ab", "abc"}
0
Returns: 3
4)
{"abacd"}
0
Returns: 1

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

Coding Area

Language: C++17 · define a public class SimilarPairs with a public method int howManyElements(vector<string> text, int k) · 229 test cases · 2 s / 256 MB per case

Submitting as anonymous