- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Suppose we have a string s and a number k. Now each character in the string is either dot ('.') or 'x', where dot indicates an empty space and 'x' indicates a person. We have to check whether it's possible to choose a position to stand on such that the distance between us and the closest person to us is at least k. (Here the distance between each neighbouring indices is 1).

So, if the input is like s = "x...x..", k = 2, then the output will be True, as we can stand at s[2] or s[6].

To solve this, we will follow these steps −

- pos := location of x in s, if not present, pos will be -1
- if pos is same as -1 or pos>=k, then
- return True

- last_x := pos
- dist_min := 2*k-1
- Do infinite loop, do
- next_x := location of x in s from index last_x+1 to end (if x is not present, it will be -1)
- if next_x is not same as -1, then
- if next_x-last_x-1 >= dist_min, then
- return True

- last_x := next_x

- if next_x-last_x-1 >= dist_min, then
- otherwise,
- if size of s -last_x-1 >= k, then
- return False

- if size of s -last_x-1 >= k, then

- return null

Let us see the following implementation to get better understanding −

class Solution: def solve(self, s, k): pos = s.find("x") if pos==-1 or pos>=k: return True last_x = pos dist_min = 2*k-1 while True: next_x = s.find("x", last_x+1) if next_x!=-1: if next_x-last_x-1 >= dist_min: return True last_x = next_x else: if len(s)-last_x-1>=k: return True return False return None ob = Solution() print(ob.solve("x...x..", 2))

"x...x..", 2

True

- Related Questions & Answers
- Check If All 1's Are at Least Length K Places Away in C++
- Program to check whether we can make k palindromes from given string characters or not in Python?
- Program to find k where k elements have value at least k in Python
- Program to check whether we can convert string in K moves or not using Python
- Program to check whether every one has at least a friend or not in Python
- Program to check whether we can reach last position from index 0 in Python
- Program to find elements from list which have occurred at least k times in Python
- Program to check whether palindrome can be formed after deleting at most k characters or not in python
- Program to check we can reach end of list by starting from k in Python
- Program to check two strings are 0 or 1 edit distance away or not in Python
- Python program to check whether we can pile up cubes or not
- Program to find maximum value of k for which we can maintain safe distance in Python
- Program to find largest average of sublist whose size at least k in Python
- Program to check whether we can take all courses or not in Python
- Program to check whether we can unlock all rooms or not in python

Advertisements