Statistics

Problem Statement for "Patterns"

Problem Statement

A "repetition pattern" describes a set of strings, all of which have the same number of letters and the same pattern of repeated letters. For example, a string satisfies the repetition pattern ABBDA if it contains exactly five letters, 3 of which are distinct, with the 1st and 5th matching and the 2nd and 3rd matching. "effze", "abbda", "zqqaz" all satisfy this pattern while "aaaaa", "abbd", and "dbbda" all fail to satisfy it. Note that the repetition pattern CAAZC describes exactly the same set of strings as does ABBDA.

Create a class Patterns that contains the method firstMatch that takes a String s and a String pat, the pattern, as inputs and returns the 0-based index in s where the first matching substring starts. If no substring of s matches pat, return -1.

Definition

Class:
Patterns
Method:
firstMatch
Parameters:
String, String
Returns:
int
Method signature:
int firstMatch(String s, String pat)
(be sure your method is public)

Constraints

  • s contains between 1 and 50 characters, inclusive.
  • Each character in s is a lowercase letter 'a'-'z'.
  • pat contains between 1 and 50 characters, inclusive.
  • Each character in pat is an uppercase letter 'A'-'Z'.

Examples

  1. "nowisthetree"

    "ABCA"

    Returns: 5

    "thet" and "etre" both satisfy the pattern ABCA. "thet" is first, starting at index 5.

  2. "abcdefghijklmnop"

    "ZYX"

    Returns: 0

    Every 3 letter substring of this string s satisfies the pattern ZYX. "abc" is first.

  3. "abcdefghijklmnop"

    "QQ"

    Returns: -1

  4. "cabbabbabbaqc"

    "ABBAC"

    Returns: 7

  5. "abba"

    "ABBAC"

    Returns: -1

  6. "aaaaxaaa"

    "ZA"

    Returns: 3

  7. "aaaaxaaa"

    "Z"

    Returns: 0

  8. "aaaaaaabbbbbbb"

    "XXXXXXXX"

    Returns: -1

  9. "aaaaaaabbbbbbbba"

    "VVVVVVVV"

    Returns: 7

  10. "cd"

    "CDCD"

    Returns: -1

    No substring of "cd" can have enough letters to match CDCD.

  11. "abab"

    "CDCD"

    Returns: 0

  12. "xyzyzyyyz"

    "ABBBB"

    Returns: -1

  13. "abcdefghijklmnopqrstuvwxyabcdefghijklmnopqrstuvwxx"

    "XEAA"

    Returns: 46

  14. "aaa"

    "AAAA"

    Returns: -1

  15. "nowisthetree"

    "ABCA"

    Returns: 5

  16. "aaaabcde"

    "ABCD"

    Returns: 3

  17. "osssswisthetree"

    "ABCA"

    Returns: 4

  18. "sdfwersdfkkleh"

    "ABBC"

    Returns: 8

  19. "abba"

    "CDDX"

    Returns: -1

  20. "aaaabcde"

    "BCDE"

    Returns: 3

  21. "abbbx"

    "AAC"

    Returns: 2

  22. "abbbbx"

    "AAC"

    Returns: 3

  23. "agg"

    "RR"

    Returns: 1

  24. "abab"

    "CDED"

    Returns: -1

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: