FastPrep
Problem · String

Closest Target Character

Learn this problem
● EasySnowflake logoSnowflakeFULLTIMEPHONE SCREEN
See Snowflake hiring insights

Problem statement

The original prompt described a string with characters such as a, b, and c, and asked for the closest c for each position. For a general version, given a string s and a single-character string target, return the index of the closest occurrence of target for every index in s.

Return answer where answer[i] is the closest target index to i. If two target indices are equally close, return the smaller index. If the target never appears, return -1 for every position.

Function

closestTargetIndices(s: String, target: String) → int[]

Complete the function closestTargetIndices in the editor.

closestTargetIndices has the following parameters:

  • String s: the input string.
  • String target: a single-character string representing the target character.

Returns

int[]: an integer array with length s.length. Each value is the closest target index for that position, or -1 when the target does not appear.

Clarifications / Corner Cases

  • Return the index of the closest target, not the character itself.
  • The output length must equal s.length.
  • If s is empty, return an empty array.
  • If target does not appear in s, return -1 for every position.
  • If s[i] is the target, answer[i] should be i.
  • If two target positions are equally close, use the smaller index.
  • The string may contain characters other than a, b, and c; the original prompt used c as the target example.
  • Matching is case-sensitive when the input contains letters with different cases.
  • The target may appear once, multiple times, consecutively, at the beginning, or at the end.
  • The string may be very long, so scanning left and right from every index may be too slow.

Follow-up / Interview Discussion

  1. If you need to answer the closest-target query for every index, what can be precomputed?
  2. If there are many repeated queries on the same string and same target, how would preprocessing help?
  3. What changes if the interviewer asks for distance instead of target index?
  4. What changes if the tie-break rule asks for the larger index instead of the smaller index?
  5. If the string arrives as a stream, can you output the exact closest target for each position immediately?
  6. If delayed output is allowed in a stream, when can earlier positions be finalized?
  7. If the stream is too large to store entirely, what information do you still need to keep?

Examples

Example 1

s = "abccabac"target = "c"return = [2, 2, 2, 3, 3, 3, 7, 7]

Index 5 is equally far from target indices 3 and 7, so the smaller index 3 is returned.

Example 2

s = "abab"target = "c"return = [-1, -1, -1, -1]

The target does not appear anywhere in the string.

Example 3

s = "caaac"target = "c"return = [0, 0, 0, 4, 4]

Index 2 is the same distance from target indices 0 and 4, so the smaller index 0 is returned.

Example 4

s = "abccba"target = "c"return = [2, 2, 2, 3, 3, 3]

Each target index returns itself; positions around the target block point to the closest edge of the block. The source screenshot's output for this example appears to list 4 for the last two positions, but by the stated rule their closest target index is 3, so this practice version uses the corrected output.

Example 5

s = ""target = "c"return = []

The output is also empty.

Constraints

  • 0 <= s.length <= 100000
  • target is a single-character string.
  • s may contain any printable ASCII characters unless otherwise specified by the interviewer.
  • Return values must be valid indices in s, or -1.

More Snowflake problems

drafts saved locally
public int[] closestTargetIndices(String s, String target) {
  // write your code here
}
s"abccabac"
target"c"
expected[2, 2, 2, 3, 3, 3, 7, 7]
checking account