TF Problem#10941

TF Problem (Editorial)

If the first character of the string is $F$ , print $- 1$ . Otherwise, find the index of the last $T$ character using binary search.

Algorithm implementation

The BinSearch function performs a binary search and returns the index of the last $T$ character.

int BinSearch(string& s)
{
  int l = 0, r = s.size();
  while (l < r)
  {
    int mid = (l + r) / 2;
    if (s[mid] == 'T') l = mid + 1;
    else r = mid;
  }
  return l - 1;
}

C++

The main part of the program. Read the input string $s$ .

cin >> s;

If the first character of the string is $F$ , print $- 1$ .

if (s[0] == 'F') cout << -1 << endl;

Print the answer.

else cout << BinSearch(s) << endl;

Java implementation

import java.util.*;
 
public class Main
{
  static int BinSearch(String s)
  {
    int l = 0, r = s.length();
    while (l < r)
    {
      int mid = (l + r) / 2;
      if (s.charAt(mid) == 'T') l = mid + 1;
      else r = mid;
    }
    return l - 1;
  }

  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    String s = con.next();
    if (s.charAt(0) == 'F') System.out.println(-1);
    else System.out.println(BinSearch(s));
    con.close();
  }
}

Java

Python implementation

The BinSearch function performs a binary search and returns the index of the last $T$ character.

def my_bin_search(s):
  l = 0; r = len(s)
  while l < r:
    mid = (l + r) // 2
    if (s[mid] == 'T'): l = mid + 1
    else: r = mid
  return l - 1;

Python

The main part of the program. Read the input string $s$ .

s = input()

If the first character of the string is $F$ , print $- 1$ .

if (s[0] == 'F'): print(-1)

Print the answer.

else: print(my_bin_search(s))

Python implementation — bisect

import bisect

Read the input string $s$ .

s = input()

If the first character of the string is $F$ , print $- 1$ .

if s[0] == 'F':
  print(-1)

Otherwise, compute and print the result.

else:

Invert the string. Now the letters are arranged in lexicographic order (' $F$ ' < ' $T$ '). Using binary search, find the position (index) of the first ' $T$ ' (the index of the ' $T$ ' that immediately follows an ' $F$ ').

  index = bisect.bisect_right(s[::-1], 'F')

Recompute the index. Determine the position of the last ' $T$ ' in the original string.

  index = len(s) - index – 1

Print the answer.

  print(index)