Dada una string cíclica str y dos enteros i y j , la tarea es contar el número mínimo de pasos necesarios para pasar de str[i] a str[j] . Un movimiento es llegar a cualquier carácter adyacente en la string y el movimiento solo se cuenta si str[start] != start[end] donde start es el índice de inicio del movimiento y end es el final (adyacente a la izquierda o a la derecha ). la derecha) índice. Dado que la string dada es circular, str[0] y str[n – 1] son adyacentes entre sí.
Ejemplos:
Entrada: str = “SSNSS”, i = 0, j = 3
Salida: 0
De izquierda a derecha: S -> S -> N -> S
De derecha a izquierda: S -> S -> SEntrada: str = «geeksforgeeks», i = 0, j = 3
Salida: 2
Acercarse:
- Comenzando desde el índice , empiezo a moverme en la dirección correcta hasta el índice j y por cada carácter visitado, si el carácter actual no es igual al carácter anterior, incremente pasos1 = pasos1 + 1 .
- De manera similar, a partir de i , empiezo a moverme en la dirección izquierda hasta el índice 0 y por cada carácter visitado, si el carácter actual no es igual al carácter anterior, incremente pasos2 = pasos2 + 1 . Una vez que se visita el índice 0 , comience a atravesar desde el índice n – 1 hasta el j e incremente el paso 2 si str [0] != str[n – 1] .
- Imprime min(paso1, paso2) al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the count of steps
// required to move from i to j
int getSteps(string str, int i, int j, int n)
{
// Starting from i + 1
int k = i + 1;
// Count of steps
int steps = 0;
// Current character
char ch = str[i];
while (k <= j) {
// If current character is different from previous
if (str[k] != ch) {
// Increment steps
steps++;
// Update current character
ch = str[k];
}
k++;
}
// Return total steps
return steps;
}
// Function to return the minimum number of steps
// required to reach j from i
int getMinSteps(string str, int i, int j, int n)
{
// Swap the values so that i <= j
if (j < i) {
int temp = i;
i = j;
j = temp;
}
// Steps to go from i to j (left to right)
int stepsToRight = getSteps(str, i, j, n);
// While going from i to j (right to left)
// First go from i to 0
// then from (n - 1) to j
int stepsToLeft = getSteps(str, 0, i, n)
+ getSteps(str, j, n - 1, n);
// If first and last character is different
// then it'll add a step to stepsToLeft
if (str[0] != str[n - 1])
stepsToLeft++;
// Return the minimum of two paths
return min(stepsToLeft, stepsToRight);
}
// Driver code
int main()
{
string str = "SSNSS";
int n = str.length();
int i = 0, j = 3;
cout << getMinSteps(str, i, j, n);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function to return the count of steps
// required to move from i to j
static int getSteps(String str, int i, int j, int n)
{
// Starting from i + 1
int k = i + 1;
// Count of steps
int steps = 0;
// Current character
char ch = str.charAt(i);
while (k <= j)
{
// If current character is different from previous
if (str.charAt(k) != ch)
{
// Increment steps
steps++;
// Update current character
ch = str.charAt(k);
}
k++;
}
// Return total steps
return steps;
}
// Function to return the minimum number of steps
// required to reach j from i
static int getMinSteps(String str, int i, int j, int n)
{
// Swap the values so that i <= j
if (j < i)
{
int temp = i;
i = j;
j = temp;
}
// Steps to go from i to j (left to right)
int stepsToRight = getSteps(str, i, j, n);
// While going from i to j (right to left)
// First go from i to 0
// then from (n - 1) to j
int stepsToLeft = getSteps(str, 0, i, n)
+ getSteps(str, j, n - 1, n);
// If first and last character is different
// then it'll add a step to stepsToLeft
if (str.charAt(0) != str.charAt(n - 1))
stepsToLeft++;
// Return the minimum of two paths
return Math.min(stepsToLeft, stepsToRight);
}
// Driver code
public static void main(String []args)
{
String str = "SSNSS";
int n = str.length();
int i = 0, j = 3;
System.out.println(getMinSteps(str, i, j, n));
}
}
// This code is contributed by ihritik
Python3
# Python3 implementation of the approach # Function to return the count of steps # required to move from i to j def getSteps( str, i, j, n) : # Starting from i + 1 k = i + 1 # Count of steps steps = 0 # Current character ch = str[i] while (k <= j): # If current character is different from previous if (str[k] != ch): # Increment steps steps = steps + 1 # Update current character ch = str[k] k = k + 1 # Return total steps return steps # Function to return the minimum number of steps # required to reach j from i def getMinSteps( str, i, j, n): # Swap the values so that i <= j if (j < i): temp = i i = j j = temp # Steps to go from i to j (left to right) stepsToRight = getSteps(str, i, j, n) # While going from i to j (right to left) # First go from i to 0 # then from (n - 1) to j stepsToLeft = getSteps(str, 0, i, n) + getSteps(str, j, n - 1, n) # If first and last character is different # then it'll add a step to stepsToLeft if (str[0] != str[n - 1]): stepsToLeft = stepsToLeft + 1 # Return the minimum of two paths return min(stepsToLeft, stepsToRight) # Driver code str = "SSNSS" n = len(str) i = 0 j = 3 print(getMinSteps(str, i, j, n)) # This code is contributed by ihritik
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the count of steps
// required to move from i to j
static int getSteps(string str, int i, int j, int n)
{
// Starting from i + 1
int k = i + 1;
// Count of steps
int steps = 0;
// Current character
char ch = str[i];
while (k <= j)
{
// If current character is different from previous
if (str[k] != ch)
{
// Increment steps
steps++;
// Update current character
ch = str[k];
}
k++;
}
// Return total steps
return steps;
}
// Function to return the minimum number of steps
// required to reach j from i
static int getMinSteps(string str, int i, int j, int n)
{
// Swap the values so that i <= j
if (j < i)
{
int temp = i;
i = j;
j = temp;
}
// Steps to go from i to j (left to right)
int stepsToRight = getSteps(str, i, j, n);
// While going from i to j (right to left)
// First go from i to 0
// then from (n - 1) to j
int stepsToLeft = getSteps(str, 0, i, n)
+ getSteps(str, j, n - 1, n);
// If first and last character is different
// then it'll add a step to stepsToLeft
if (str[0] != str[n - 1])
stepsToLeft++;
// Return the minimum of two paths
return Math.Min(stepsToLeft, stepsToRight);
}
// Driver code
public static void Main()
{
string str = "SSNSS";
int n = str.Length;
int i = 0, j = 3;
Console.WriteLine(getMinSteps(str, i, j, n));
}
}
// This code is contributed by ihritik
PHP
<?php
// PHP implementation of the above approach
// Function to return the count of steps
// required to move from i to j
function getSteps($str, $i, $j, $n)
{
// Starting from i + 1
$k = $i + 1;
// Count of steps
$steps = 0;
// Current character
$ch = $str[$i];
while ($k <= $j)
{
// If current character is different
// from previous
if ($str[$k] != $ch)
{
// Increment steps
$steps++;
// Update current character
$ch = $str[$k];
}
$k++;
}
// Return total steps
return $steps;
}
// Function to return the minimum number
// of steps required to reach j from i
function getMinSteps($str, $i, $j, $n)
{
// Swap the values so that i <= j
if ($j < $i)
{
$temp = $i;
$i = $j;
$j = $temp;
}
// Steps to go from i to j (left to right)
$stepsToRight = getSteps($str, $i, $j, $n);
// While going from i to j (right to left)
// First go from i to 0 then
// from (n - 1) to j
$stepsToLeft = getSteps($str, 0, $i, $n) +
getSteps($str, $j, $n - 1, $n);
// If first and last character is different
// then it'll add a step to stepsToLeft
if ($str[0] != $str[$n - 1])
$stepsToLeft++;
// Return the minimum of two paths
return min($stepsToLeft, $stepsToRight);
}
// Driver code
$str = "SSNSS";
$n = strlen($str);
$i = 0;
$j = 3;
echo getMinSteps($str, $i, $j, $n);
// This code is contributed by aishwarya.27
?>
Producción:
0
Publicación traducida automáticamente
Artículo escrito por Sumit bangar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA